Home

Functional description of MINTO, a Mixed INTeger Optimizer Version

Contents

1. nzcnt sizeof double j lt vent j I for i 0 i lt ccnt i kx _csenseli _crhs i vstorsz vcnt cstorsz ccnt _vstore char _cstore char _vname char _cname char x Es 1 0 calloc calloc calloc calloc vstorsz sizeof char cstorsz sizeof char vcnt sizeof char ccnt sizeof char 26 for j 0 j lt vcnt j I _vstore j 0 _vname j amp _vstore j for i 0 i lt ccnt i _cstore i 0 _cname i amp _cstore i vobj _vobj vlb vlb vub _vub vtype _vtype csense csense crhs _crhs vfirst _vfirst xvind _vind vcoef vcoef vstore vstore vname vname cstore cstore cname cname return NO 6 3 applinit This function provides the application with an entry point in the program to perform some initial actions It has to return either STOP in which case MINTO aborts or CONTINUE in which case MINTO continues PARAMETERS id An integer containing the identification of the active MINTO copy The following example shows how appl init can be used to open a log file E INIT C tinclude lt stdio h gt include minto h FILE fp log 27 appl_init unsigned appl init id int id identification of active minto 1 if fp_log fopen EXAMPLE LOG w NULL 1 fpri
2. int i j double minlhs maxlhs coef inq form O for i 0 i info form form ccnt i I minlhs maxlhs double O0 inq constr i for j 0 j lt info constr constr nz j ing_var info_constr constr_ind j NO if coef info_constr constr_coef j gt EPS minlhs coef info_var var_lb maxlhs coef info_var var_ub else minlhs coef info_var var_ub maxlhs coef info_var var_lb if info constr constr sense G amp amp minlhs gt info_constr constr_rhs EPS info_constr constr_status DELETE set_constr i if info_constr constr_sense L amp amp maxlhs lt info_constr constr_rhs EPS 4 info_constr constr_status DELETE set_constr i 30 6 6 appl_node This function provides the application with an entry point in the program after MINTO has selected a node from the set of unevaluated nodes of the branch and bound tree and before MINTO starts processing the node It has to return either STOP in which case MINTO aborts or CONTINUE in which case MINTO continues PARAMETERS id An integer containing the identification of the active MINTO copy depth A long containing the depth in the branch and bound tree of the node that has been selected for evaluation creation A long containing the creation number of the node that has been selected for evaluation zprimal A double containing the value of the primal solution xprimal An a
3. double zprimal value of primal solution double xprimal value of the variables int ecnt number of evaluated nodes double gap gap between primal and LP solution value printf Number of variables in active lp d n CPXgetnumcols mintoenv mintolp printf Number of constraints in active lp d n CPXgetnumrows mintoenv mintolp return CONTINUE 11 2 OSI Direct Access to the OSI LP Solver is not available in Version 3 1 Subsequent versions will be enabled with this feature 12 Environment variables MINTO provides some control over its activities through the use of environment variables Most of the environment variables affect memory management and row management activities 62 MIOSDIM MIOLDIM MIOBDIM MINTO tries to keep memory management fully within MINTO There fore the arrays passed to an application function to hold information to be passed back to MINTO have a fixed length either sdim Idim or bdim These lengths can be changed by setting the corresponding environment variable MIOSTORAGE For efficiency MINTO maintains all its data structures in internal memory Consequently MINTO requires a huge amount of internal memory when for some problem instance the branch and bound tree gets really big Setting the environment variable MIOSTORAGE to 1 will direct MINTO to store part of its data structures externally to free up internal memory This considerably reduces t
4. nzent vent vclass vobj vlb vub vfirst vind vcoef vname sdim ldim An integer containing the identification of the active MINTO copy A double containing the value of the LP solution An array of doubles containing the values of the variables A double containing the value of the primal solution An array of doubles containing the values of the variables associated with the primal solu tion An integer to hold the number of nonzero coefficients to be added to the current formulation An integer to hold the number of variables to be added to the current formulation An array to hold the classification of variables to be added to the current formulation i e BINARY INTEGER CONTINUOUS An array of doubles to hold the objective function coefficients of the variables to be added An array of doubles to hold the lower bounds on the values of the variables to be added An array of doubles to hold the upper bounds on the values of the variables to be added An array of integers to hold the positions of the first nonzero coefficients of the variables to be added An array of integers to hold the row indices of the nonzero coefficients of the variables to be added An array of doubles to hold the values of the nonzero coefficients of the variables to be added An array of character pointers to hold the names of the variables to be added An integer to hold the length of the arrays vobj varlb varub and vfirst
5. An integer to hold the length of the arrays vind and vcoef For reasons having to do with memory management the application has to allocate the memory using 32 calloc to hold the name associated with a variable MINTO will free that memory after it has installed the name in its internal administration The following example shows how appl variables can be used to implement a column generation scheme for the solution of the linear program E VARS C tinclude lt stdio h gt include minto h appl_variables unsigned appl variables id zlp xlp zprimal xprimal nzcnt vcnt vclass vobj varlb varub vfirst vind vcoef vname sdim ldim int id identification of active minto double zlp value of the LP solution double xlp values of the variables double zprimal value of the primal solution double xprimal values of the variables int nzcnt variable for number of nonzero coefficients int vcnt variable for number of variables char vclass array for classifications of vars added double vobj array for objective coefficients of vars added double varlb array for lower bounds of vars added double varub array for upper bounds of vars added int vfirst array for positions of first nonzero coefficients int vind array for indices of nonzero coefficients double vcoef array for values of nonzero coefficients ch
6. The following example shows how appl initlp can be used to indicate that column generation will be used to solve the linear programming relaxations E_INITLP C include lt stdio h gt include minto h appl initlp 28 unsigned appl initlp id colgen int id identification of active minto int colgen indicator colgen TRUE return CONTINUE 6 5 appl preprocessing This function provides the application with an entry in the program to perform preprocessing based on the original formulation It has to return either STOP in which case assumes infeasibility has been detected or CONTINUE in which case MINTO continues The function appl_preprocessing is called once after the original formulation has been read and at each node of the search tree before the evaluation of the node begins PARAMETERS id An integer containing the identification of the active MINTO copy In general MINTO only stores data in the information variables associated with the inquiry functions and never looks at them again i e communication between MINTO and the application program is one way only However in appl_preprocessing a set of modification functions can be used by the application program to turn this one way communication into a two way communication A call to a modification function signals that the associated variable has been changed by the application and that MINTO should retrieve the data
7. agzy lt 0 BINSUMIVAREQ jenta tj ete BINSUMIUB jep tj lt 1 BINSUM1EQ jer xj 1 Table 3 Constraint classes constraint are valid at any node of the branch and bound tree whereas local constraints are only valid in the subtree rooted at the node where the constraints are generated Constraints can be in one of three states active inactive or deleted Active constraints are part of the active formulation Inactive constraints have been deactivated but may be reactivated at a later time Deleted constraints have been removed altogether Variables When solving a linear program MINTO allows for column generation In other words after a linear program has been optimized MINTO asks for the pricing out of variables not in the current formulation If any such variables exists and price out favorably they are included in the formulation and the linear program is reoptimized Branching The unevaluated nodes of the branch and bound tree are kept in a list and MINTO always selects the node at the head of the list for processing However there is great flexibility here since MINTO provides a mechanism that allows an application program to order the nodes in the list in any way 4 System Functions MINTO s system functions are used to perform preprocessing probing constraint generation and reduced price variable fixing to enhance branching and to produce primal feasible solutions They may be employed at
8. if info_base base_vstat j BASIC ing var j NO if info var var class CONTINUOUS 1b ub if if info var info var 1b gt ub continue var lb var ub EPS 4 x1p j lt 1b EPS amp amp zlp lp rc j lt zprimal EPS 4 vind vent j 42 vtype vcnt U vvalue vcnt 1b if vcnt bdim break if xlp j gt ub EPS amp amp zlp lp rc j lt zprimal EPS vind vcnt zs vtype vcnt L vvalue vent ub if vcnt bdim break return vcnt gt 0 SUCCESS FAILURE 6 14 appl constraints This function allows the application to generate one or more violated constraints It has to return either FAILURE in which case MINTO assumes that no violated constraints were found or no attempt was made to generate any and it therefore ignores the parameters nzent cent cfirst cind ccoef and ctype or SUCCESS in which case MINTO assumes that additional constraints have been found by the application and that they are available through the parameters nzcnt cent cfirst cind ccoef and ctype PARAMETERS id An integer containing the identification of the active MINTO copy zlp A double containing the value of the LP solution xlp An array of doubles containing the values of the variables zprimal A double containing the value of the primal solution xprimal An array of doubles containing the values of the variables a
9. c n info_constr constr_sense printf RHS Zf n info constr constr rhs printf CLASS s n ConvertCClass info_constr constr_class printf TYPE s n ConvertCType info constr constr type printf STATUS s n ConvertStatus info constr constr status printf INFO Zs n ConvertCInfo info constr constr info printf VARIABLES n for i 0 i lt info_form form_vcnt i I printf d n i ing_var i TRUE if info_var var_name printf NAME fan info var var name else printf NAME no name n for j 0 j lt info_var var_nz j printf 4f dNn info_var var_coef j info_var var_ind j printf OBJ Zf n info var var obj printf CLASS sWn ConvertVClass info_var var_class printf STATUS s n ConvertStatus info var var status printf LB WfNn info var var 1b printf UB Zf n info var var ub printf INFO LB s n ConvertVInfo info var var lb info printf INFO UB s n ConvertVInfo info var var ub info if info var var vlb 4 printf VLB f d n info var var vlb gt vlb val info var var vlb gt vlb var else printf NO VLB n if info_var var_vub printf VUB f d n 67 info_var var_vub gt vub_val info var var vub gt vub var else printf NO VUB n printf n static char bsiu BINSUM1UB static char bsle
10. cfirst ccnt nzcnt cind nzcnt INDEX i j ccoef nzcnt 1 0 cind nzcnt INDEX j k ccoef nzcnt 1 0 cind nzcnt INDEX k i ccoef nzcnt 1 0 csense ccnt oL crhs ccnt 2 0 ctype ccnt GLOBAL if ccnt sdim nzcnt gt ldim 3 I goto EXIT EXIT cfirst ccnt nzcnt return ccnt gt 0 SUCCESS FAILURE 6 15 appl delconstraints This function allows the application to delete one or more of the previously generated constraints from the active formulation i e the formulation currently loaded in the LP solver It has to return either FAIL URE in which case MINTO assumes that no constraints have to be deleted and it therefore ignores the parameters cent and cind or SUCCESS in which case MINTO assumes the constraints have to be deleted and that these constraints are available through the parameters cent and cind PARAMETERS id An integer containing the identification of the active MINTO copy 45 cent An integer to hold the number of constraints to be deleted from the active formulation cind An array of integers to hold the indices of the constraints to be deleted from the active formulation Note that constraints are deleted from the active formulation Therefore indices are considered to be relative to the active formulation Note also that it is only possible to delete previously generated con straints either by MINTO or by t
11. printf ERROR in appl_init id gt 1 n exit 1 return CONTINUE E_CONS C include lt stdio h gt include minto h appl_constraints unsigned appl_constraints nzcnt ccnt int id double zlp double xlp double zprimal double xprimal int nzcnt int ccnt int cfirst id zlp xlp zprimal xprimal cfirst cind ccoef csense crhs ctype cname sdim ldim identification of active minto value of the LP solution values of the variables value of the primal solution values of the variables variable for number of nonzero coefficients variable for number of constraints array for positions of first nonzero coefficients 60 int cind array for indices of nonzero coefficients double ccoef array for values of nonzero coefficients char csense array for senses double crhs array for right hand sides int ctype array for the constraint types LOCAL or GLOBAL char cname array for names int sdim length of small arrays int ldim length of large arrays switch id case 0 Invoke MINTO to solve the separation problem This assumes that other application functions such as appl_mps have been set up properly to define the separation problem minto separation s Print the solution printf Optimal value
12. vvalue An array of doubles to hold the values of the bounds nzent An integer to hold the total number of nonzero coefficients in the constraints generated for each node cent An array of integers to hold the number of constraints generated for each node cfirst An array of integers to hold the positions of the first nonzero coefficients of the constraints generated cind An array of integers to hold the indices of the nonzero coefficients of the constraints gener ated ccoef An array of doubles to hold the values of the nonzero coefficients of the constraints gener ated csense An array of characters to hold the senses of the constraints generated crhs An array of doubles to hold the right hand sides of the constraints generated cname An array of character pointers to hold the names of the constraints to be added bdim An integer containing the length of the arrays vind vtype and vvalue sdim An integer containing the length of the arrays cent cfirst csense and crhs ldim An integer containing the length of the arrays cind and ccoef The default division scheme partitions the set of solutions into two sets by specifying bounds for the integer variable with fractional part closest to 0 5 In the first set of the partition the selected variable is bounded from above by the round down of its value in the current LP solution In the second set of 48 the partition the selected variable is bounded from below by the roun
13. ACTIVE INACTIVE or DELETED Constraint type is one of LOCAL or GLOBAL Constraint information is one of ORIGINAL GENERATED BY BRANCHING GENERATED BY MINTO and GENERATED BY APPL PARAMETERS index An integer containing the index of the constraint A call to ing constr initializes the variable info constr that has the following structure typedef struct info constr char constr name name if any int constr class classification int constr nz number of variables with nonzero coefficients int constr ind indices of variables with nonzero coefficients double constr coef actual coefficients char constr sense sense double constr rhs right hand side int constr status ACTIVE INACTIVE or DELETED int constr type LOCAL or GLOBAL int constr info ORIGINAL GENERATED BY MINTO GENERATED BY BRANCHING or GENERATED BY APPL INFO CONSTR 17 The following example shows how inq_constr can be used to print the types of the constraints in the current formulation E_TYPE C include lt stdio h gt include minto h WriteType void WriteType O int i for ing_form i 0 i lt info_form form_ccnt i I ing_constr i printf Constraint d is of type s n i info_constr constr_type GLOBAL GLOBAL LOCAL 5 2 ing prob This function retrieves the name of the problem that is being solved
14. i e the name found in the NAME section of the lt problem name gt mps file that was read when MINTO was invoked The following example shows how ing prob can be used to print the name of the problem being solved E_NAME C include lt stdio h gt include minto h WriteName void WriteName 1 printf Problem name s n inq prob O 18 A more elaborate example showing how the inquiry functions can be used to print everything there is to know about the current formulation can be found in Appendix A 5 3 Active formulation Information about the LP solution to the active formulation and information about the best primal so lution are available to the application whenever appropriate through the parameters passed to the application functions Additional information about the active formulation and the LP solution can be obtained through the inquiry functions Ip vent Ip cent Ip slack Ip pi Ip rc and Ip base MINTO gets the required information directly from the LP solver Therefore the user is referred to the manual of the LP solver for a precise definition of the return values For example the manual of the LP solver defines the meaning of the values of the dual variables in case the linear program is infeasible 5 3 1 lp vent This function returns the number of variables in the active formulation i e the number of variables currently loaded in the LP solver 5 3 2 Ip cent This fun
15. BINSUM1IEQ static char bsivu BINSUM1VARUB static char bsive BINSUM1VAREG static char bsvu BINSUMVARUB static char bsve BINSUMVAREQ static char svu SUMVARUB static char sve SUMVAREQ static char vu VARUB static char ve VAREQ static char vl VARLB static char mixu MIXUB static char mixe MIXEQ static char nbu NOBINUB static char nbe NOBINEQ static char abu ALLBINUB static char abe ALLBINEQ ConvertCClass Convert the constraint class into a printable string char ConvertCClass class int class switch class case BINSUM1UB return bsiu case BINSUM1EQ return bsie case BINSUM1VARUB return case BINSUM1VAREQ return bsive bsivu 68 case BINSUMVARUB return bsvu case BINSUMVAREQ return bsve case SUMVARUB return svu case SUMVAREQ return sve case VARUB return vu case VAREQ return ve case VARLB return v1 case MIXUB return mixu case MIXEQ return mixe case NOBINUB return nbu case NOBINEQ return nbe case ALLBINUB return abu case ALLBINEQ return abe static char local LOCAL static char global GLOBAL ConvertCType Convert the constraint type into a printable string char ConvertCType type int type switch type case LOCAL return local case GLOBAL return global
16. change the amount of output generated by MINTO There are four output levels no 0 very little 1 normal 2 and extensive 3 Future versions of MINTO will work on divorcing completely any dependence on the LP solver from the MINTO library option effect x assume maximization problem o lt 0 1 2 3 gt level of output m lt gt maximum number of nodes to be evaluated feum maximum cpu time in seconds b deactivate bound improvement e 0 1 2 3 4 5 type of branching E lt 0 1 2 3 4 gt type of node selection p lt 0 1 2 3 gt level of preprocessing and probing h deactivate primal heuristic deactivate clique generation deactivate implication generation deactivate knapsack cover generation deactivate GUB cover generation deactivate flow cover generation deactivate row management deactivate restarts lt 0 1 2 gt type of forced branching deactivate all system functions n lt 1 2 3 gt activate a names mode a activate use of advance basis u W DR 0 TT o Table 1 Command line options In default mode MINTO performs preprocessing and limited probing if the number of binary variables is not too large For a description of preprocessing and probing and all other system functions see Section 4 The p lt 0 1 2 3 gt command line option can be used to change the amount of preprocessing and probing done by MINTO There are four levels no preprocessing and no probing 0 preprocessing but no
17. depth long creation node identification creation double zlp value of the LP solution double zprimal value of the primal solution double rank rank value if switched TRUE rank zlp return SUCCESS else if zprimal lt 1 0 EPS INF rank double creation return SUCCESS else 53 rank zlp switched TRUE return REORDER 6 19 appl exit This function provides the application with an entry point in the program to perform some final actions MINTO ignores the return value PARAMETERS id An integer containing the identification of the active MINTO copy zopt A double containing the value of the final solution xopt An array of doubles containing the values of the variables associated with the final solution If no solution vector exists the second parameter will be NULL The following example shows how the function appl_exit can be used to write the optimal solution to a log file and afterwards close the log file E EXIT C include lt stdio h gt include minto h extern FILE fp_log appl_exit unsigned appl_exit id zopt xopt int id identification of active minto double zopt value of the final solution double xopt values of the variables int j fprintf fp log OPTIMAL SOLUTION VALUE f n zopt if xopt I fprintf fp log OPTIMAL SOLUTION Nn for ing form j 0 j l
18. every node of the branch and bound tree However their use is optional A more detailed description of some of the system functions embedded in MINTO can be found in the papers listed in the references In preprocessing MINTO attempts to improve the LP relaxation by identifying redundant constraints 12 detecting infeasibilities tightening bounds on variables and fixing variables using optimality and feasibil ity considerations For constraints with only 0 1 variables it also attempts to improve the LP relaxation by coefficient reduction For example a constraint of the form aigi a229 a3x3 lt ag may be replaced by a4z4 asa a3 6 x3 ag for some gt 0 that preserves the set of feasible solutions In probing MINTO searches for logical implications of the form x 1 implies y v and stores these in an implication table Furthermore MINTO uses the logical implications between binary variables to build up a clique table i e MINTO tries to extend relations between pairs of binary variables to larger sets of binary variables After a linear program is solved and a fractional solution is obtained MINTO tries to exclude these solutions by searching the implication and clique table for violated inequalities and by searching for violated lifted knapsack covers violated lifted GUB covers and violated lifted simple generalized flow covers Lifted knapsack covers are derived from pure 0 1 constraints and are
19. for the arrays that are passed as parameters to an application function However from an application program point of view they are fixed length arrays When appropriate the current lengths of the arrays are also passed as parameters It is the responsibility of the application program to ensure that memory is not overrun MINTO will abort immediately if it detects a memory violation 14 Availability and Future Releases MINTO 3 1 is currently available for the platforms in Table 4 If you would like your Operating System and LP Solver added to the list please contact the mantainers Operating System Architecture Compiler LP Solver Debian Linux Intel x86 g 3 3 5 CPLEX v8 Debian Linux Intel x86 g 3 3 5 OSI Clp MS Windows XP Intel x86 MS Visual C NET CPLEX v8 Table 4 Available MINTO Versions MINTO is an evolutionary system and therefore version 3 1 is not a final product We see the devel opment of MINTO as an evolutionary process that should lead to a robust and flexible mixed integer programming solver It s modular structure makes it easy to modify and expand especially with regard to the addition of new information and application functions Therefore we encourage the users of this release to provide us with comments and suggestions for future releases Developments in future releases may include parallel implementations more efficient cut generation routines additional classes of cuts explicit column
20. in describing and understanding MINTO MINTO is con stantly manipulating formulations storing a formulation retrieving a formulation modifying a formula tion duplicating a formulation handing a formulation to the LP solver providing information about the formulation to the application program etc We will always use the following terms to refer to elements of a formulation objective function constraint coefficient sense right hand side variable lower bound and upper bound It is beneficial to distinguish four types of formulations The original formulation is the formulation specified in the lt problemname gt mps file The initial formulation is the formulation associated with the root node of the branch and bound tree It may differ from the original formulation as MINTO automatically tries to improve the initial formulation using various preprocessing techniques such as detection of redundant constraints and coefficient reduction The current formulation is an extension of the original formulation and contains all the variables and all the global and local constraints associated with the node that is currently being evaluated The active formulation is the formulation currently loaded in the LP solver It may be smaller that the current formulation due to management of inactive constraints It is very important that an application programmer realizes that the active formulation does not nec essarily coincide with his mental picture
21. maximum number of columns that has been in the active linear program 5 5 9 stat cliquecnt This function returns the number of clique inequalities that has been generated 21 5 5 10 stat implicationcnt This function returns the number of implication inequalities that has been generated 5 5 11 stat knapcovent This function returns the number of lifted knapsack cover inequalities that has been generated 5 5 12 stat gubcovcnt This function returns the number of lifted GUB cover inequalities that has been generated 5 5 13 stat sknapcovent This function returns the number of surrogate lifted knapsack cover inequalities that has been generated 5 5 14 stat flowcovent This function returns the number of lifted flow cover inequalities that has been generated 5 5 15 stat time This function returns the elapsed cpu time 6 Application Functions A main program sometimes called a driver and a set of application functions either the default or any other has to be compiled and linked with the MINTO library in order to produce an executable version of MINTO The application functions give the user the opportunity to incorporate problem specific knowledge and thereby increase the overall performance A default set of application functions is part of the distribution of MINTO The incorporation of these default functions turns MINTO into a general purpose mixed integer optimizer Internally MINTO always works with a maximizatio
22. of the formulation since MINTO may have generated additional constraints temporarily deactivated constraints or fixed one or more variables Constraints MINTO distinguishes various constraint classes as defined in Table 2 These constraint classes are mo tivated by the constraint generation done by MINTO and the branching scheme adopted by MINTO To present these constraint classes it is convenient to distinguish the binary variables We do this by using the symbol y to indicate integer and continuous variables Each class is an equivalence class with respect to complementing binary variables i e if a constraint with term a x is in a given class then the con straint with aja replaced by a 1 x is also in the class For example Ye g 2 jeg tj 1 B is in the class BINSUM1UB where we think of B as the set of complemented variables Besides constraint classes MINTO also distinguishes two constraint types global and local Global AddVars AddCons GetProblem i Preprocess Select i iix oen d Preprocess LP 1 Delete Vars 1 AME e Ea c DoPriceVars gt KE SO port NZ id I Price Vars i Late Gols rs A lt Integral y 5 n e e y n n r ae ok PrimalHeuristic t UC SY We ofr
23. pro cess either by MINTO or by an application note that MINTO only generates global constraints and if the value of a dual variable has been equal to zero implying the constraint is inactive for ten consecutive iterations MINTO will deactivate the corresponding constraint Deactivating a constraint means deleting it from the active formulation and storing it in the cut pool Every time the active formulation is solved and a new linear programming solution exists the constraints in the cut pool will be inspected to see if any of them are violated by the current solution If so these constraints will be reactivated Reactivating a constraint means adding it to the active formulation and deleting it from the cut pool The cut pool has a fixed size and is maintained on a first in first out basis i e if the pool overflows the constraints that have been in the pool the longest will be deleted As soon as a cut is deleted from the cut pool it can never be reactivated again The environment variable MIOCUTPOOLSZ sets the size of the pool default size is 250 The environment variable MIOCUTDELBND sets the the deactivation threshold default threshold is 50 MIOCUTFREQ Another issue related to cut generation is the frequency with which an attempt is made to generate cuts Obviously cut generation takes time and it may be beneficial not to perform cut generation at every node of the search tree The environment variable MIOCUTFREQ sets the frequency with
24. section we describe the process of obtaining and unpacking MINTO how to build and run an executable with the MINTO libraries and how to create a minto solver that will work with the AMPL modeling language 2 1 Obtaining MINTO MINTO libraries application source files and AMPL application source files can be downloaded from the MINTO web site http coral ie lehigh edu minto In order to access the MINTO repository we require that the user provide a valid email address so that we can better track the community of users We will never distribute these email addresses to anyone The name of the downloaded file contains the minto version the computer operating system and the linear programming software for which the library is built 2 2 Building MINTO In order to create a minto executable the user application files in the directory APPL must be compiled and linked with the minto library 1ibminto a that comes with the distribution Prior to linking the user application functions can be modified to customize the branch and cut or branch and price algorithm as described in Section 3 A Makefile is included in the APPL directory of the distribution for this purpose 2 3 Running MINTO The following command should be used to invoke MINTO minto xo lt gt m lt gt t lt gt be lt gt E lt gt p lt gt hcikgfrRB lt gt sn lt gt a lt name gt where lt name gt is the name of an MPS formatted file It is also possible to generate the m
25. than their commercial counterparts MINTO is one such framework that can be used to solve large mixed integer programs efficiently without having to develop a full blown special purpose code in each case MINTO is an effective gen eral purpose mixed integer optimizer that can be customized through the incorporation of application functions Its strength is that it allows users to concentrate on problem specific aspects rather than data structures and implementation details such as linear programming and branch and bound The heart of MINTO is a linear programming based branch and bound algorithm It can be imple mented on top of any LP solver that provides capabilities to solve and modify linear programs and inter pret their solutions The current version can either be built on top of the CPLEX callable library version 6 0 and up or on top of the COIN OR OsiSolverInterface see http www coin or org Currently only the Coin Linear Programming toolkit C1p is implemented through OSI but in subsequent releases more of the 11 different linear programming toolkits that have an OsiSolverInterface will be imple mented through MINTO To be as effective and efficient as possible when used as a general purpose mixed integer optimizer MINTO attempts to e improve the formulation by preprocessing and probing e construct feasible solutions e generate strong valid inequalities e perform variable fixing based on reduced prices e control the siz
26. underlying LP solver that is used to write the MPS file will be written to the MINTO log file 10 Calling MINTO recursively In many branch and cut and branch and price algorithms the separation and pricing problems are them selves difficult mixed integer programs MINTO supports the development of such algorithms since it can be called recursively Each time MINTO is called it checks to see if it is called recursively i e from within another running copy of MINTO If MINTO has not been called recursively it assigns itself the identification 0 If on the other hand it has been called recursively it assigns itself the next available identification i e the identification of the calling copy of MINTO plus one Consequently MINTO s identification represents the depth of the recursion The recursion depth gives users the opportunity to develop multiple customized versions of MINTO at the same time The first parameter passed to every application function is the identification of the currently active copy of MINTO This allows the implementation of application functions that perform different actions based upon the recursion depth as the following examples show E_INIT C 59 include lt stdio h gt include minto h appl init unsigned appl init id int id switch id case 70 printf Initializing master problem n break case 71 printf Initializing subproblem n break default
27. which an attempt is made to generate cuts default frequency is 1 i e cut generation at every node MIOPRIMALFREQ Determining primal feasible solutions is of crucial importance for the performance of branch and bound algorithms MINTO uses a diving heuristic to try and find feasible solutions Obvi ously the diving heuristic takes time and it is therefore impractical to invoke it at every node of the search 63 tree The environment variable MIOPRIMALFREQ sets the frequency with which the diving heuristic is invoked If not set explicity MINTO will automatically and dynamically determine how often to invoke the diving heuristic based on the gap between the lower and upper bounds on an optimal solution MIOMAXLPDIVING This parameter limits the number of linear programs that are solved by the diving heuristic The default value is 50 13 Programming considerations The include file minto h is and should always be included in all sources of application functions since it contains constant definitions type definitions external variable declarations and function prototypes The variables and arrays containing information about the LP solution associated with the active for mulation and information about the best primal solution which are passed as parameters to the applica tion functions are the ones maintained by MINTO for its own use They should never be modified they should only be examined MINTO allocates memory dynamically
28. 000 AMPL A Modeling Language for Mathematical Programming The Scientific Press 65 Appendix A Inquiry functions E_UTIL C include minto h ifdef PROTOTYPING void WriteFormulation void char ConvertCClass int char ConvertCType int char ConvertCInfo int char ConvertVClass int char ConvertVInfo int char ConvertStatus int ttelse void WriteFormulation char ConvertCClass char ConvertCType char ConvertCInfo char ConvertVClass 0 char ConvertVInfo 0 char ConvertStatus endif WriteFormulation WriteFormulation is an example of the use of the inquiry functions provided by MINTO to access the formulation in the current node of the branch and bound tree void WriteFormulation int i j printf n nCURRENT FORMULATION Nn printf NAME s n inq prob printf OBJECTIVE n for ing obj j 0 j lt info_obj obj_nz j I printf 4f dNn info_obj obj_coef j info obj obj ind j printf CONSTRAINTS n for ing_form i 0 i lt info_form form_ccnt i I 66 printf d n i ing_constr i if info_constr constr_name printf NAME 4sNn info constr constr name else printf NAME no name n for j 0 j lt info constr constr nz j printf f dNn info_constr constr_coef j info_constr constr_ind j printf SENSE
29. 69 ORIGINAL GENERATED BY MINTO GENERATED BY BRANCHING GENERATED BY APPL static char original static char genminto static char genbranch static char genappl ConvertCInfo Convert the constraint status into a printable string char ConvertCInfo info int info switch info case ORIGINAL return original case GENERATED_BY_MINTO return genminto case GENERATED_BY_BRANCHING return genbranch case GENERATED_BY_APPL return genappl h h static char cont CONTINUOUS static char bin BINARY static char integ INTEGER ConvertVClass Convert the variable class into a printable string char ConvertVClass class int class switch class case CONTINUOUS return cont case BINARY return bin 70 case INTEGER return integ static char modminto MODIFIED BY MINTO MODIFIED BY BRANCHING MODIFIED BY APPL static char modbranch static char modappl ConvertVInfo Convert the constraint status into a printable string char ConvertVInfo info int info switch info I case ORIGINAL return original case MODIFIED BY MINTO return modminto case MODIFIED_BY_BRANCHING return modbranch case MODIFIED_BY_APPL return modappl static char act ACTIVE static char inact INACTIVE static char del DELETED ConvertStatus Conv
30. An integer specifying the pricing algorithm i e for the primal simplex algorithm REDUCED_COST REDUCED_COST_DEVEX DEVEX STEEPEST_EDGE SLACK NORMS or FULL and for the dual simplex algorithm AUTO STANDARD DUAL STEEPEST_EDGE STEEPEST_EDGE_SLACK or STEEPEST_EDGE_NORMS 7 6 ctrl Ippricinglist This function sets the size of the pricing list maintained by the LP solver PARAMETERS CPLEX size An integer specifying the size of the pricing list 7 7 ctrl lpperturbconst This function sets the constant used the LP solver when it perturbs the active linear program PARAMETERS CPLEX value A double specifying the value of the perturbation constant 7 8 ctrl Ipperturbmethod This function selects the perturbation method used by the LP solver PARAMETERS CPLEX selector An integer specifying the perturbation method i e BEGINNING or AUTOMATIC 7 9 ctrl Iprefactorfreq This function sets the refactorization frequency PARAMETERS CPLEX freq An integer specifying the frequency of refactorization 57 8 Bypass functions MINTO provides advanced low level control over the flow of control through a set of bypass functions Each of these control functions can be called any time during the solution process and determines whether or not certain system activities are carried out or not These functions affect the main flow of control and should be used very carefully 8 1 bypass lp This function allows an application to bypass
31. ETED Variable information is one of ORIGINAL MODIFIED BY BRANCHING MODI FIED BY MINTO and MODIFIED BY APPL These constants are defined in the header file ninto h which is included in the APPL directory of the distribution and mu8st be included in every application source file PARAMETERS index An integer containing the index of the variable colinfo A boolean indicating whether the column associated with the variable should be retrieved or not i e YES or NO A call to inq var initializes the variable info var that has the following structure typedef struct info var 4 char var name name if any char var class class CONTINUOUS INTEGER or BINARY double var obj objective function coefficient int var nz number of constraints with nonzero coefficients int var ind indices of constraints with nonzero coefficients double var coef actual coefficients int var status ACTIVE INACTIVE or DELETED double var lb lower bound double var ub upper bound VLB var vlb associated variable lower bound VUB var_vub associated variable upper bound int var lb info ORIGINAL MODIFIED BY MINTO MODIFIED BY BRANCHING or MODIFIED BY APPL int var ub info ORIGINAL MODIFIED BY MINTO MODIFIED BY BRANCHING or MODIFIED BY APPL INFO VAR typedef struct int vlb_var index of associated 0 1 variable double vlb_val value of
32. Functional description of MINTO a Mixed INTeger Optimizer Version 3 1 Martin W B Savelsbergh George L Nemhauser Georgia Institute of Technology School of Industrial and Systems Engineering Atlanta GA 30332 0205 USA Current Maintainer Jeff T Linderoth Lehigh University Department of Industrial and Systems Engineering Bethlehem PA 18015 USA martin savelsbergh isye gatech edu george nemhauser isye gatech edu jtl3 lehigh edu February 2005 Contents 1 Introduction 2 Using MINTO 2 1 2 2 2 3 2 4 Obtaining MINTO a A UTD er Ayr SR ee dl Re Roe E Peg Building MINTO Graces ho Pee pepe STG BE A Keane ERRARE Running MINTO 4 Sa a tet JAKE SSE ee SA A WA ae qp ee Using MINTO Through AMPL rage n ees 3 System design 4 System Functions 5 Information Functions 5 1 5 2 5 3 5 4 5 5 Current formulation ese TEDE TESE GEN pes de dd GR Rege E RC GE Sa dnq fOri ses A EA gn Gad ANE Sa Gled petes fa 512 ANG Wat x 4S Go Pa eee ds SEAT See EN SAGE 5 1 3 inq ob sa sog 3 ea aar am ue Ud GE ae do TRES E 5 1 4 4nq COnSLE 1 5 A ok PE NS SAR AT ute toes inq prob sv vgs sen skrot ER PG REO RU FA ae RA ELE Active form latiomn e ME pea a A ee Get SnI Pvt 4x zT REOS E pledd GE ek be Rss 532 peent oo gcc ee a A RAS BA bunte m E Re RC 5 33 Ip slack i one 8 daa A Ry me Ps d ees SG 5 3 4 RN SN Rr re STE REIR S EN FANS red 5 3 0 19 base ici as A SUG EPLET DAA A ev Names mode uo Di E A Eee des
33. INTO Through AMPL The directory APPL AMPL contains source files necessary for building a MINTO solver capable of inter facing with the AMPL modeling language 9 In order to use this feature besides libraries for linear programming the user must have installed and built the AMPL solver libraries that are available at ftp netlib bell labs com netlib ampl In the APPL AMPL directory there is a Makefile that can be used to build a solver executable mintoamp that can be set as the active solver from within AMPL using the command option solver mintoamp Table 2 contains a list of the minto options that can be set through AMPL Figure 1 gives two examples of setting various MINTO options through the AMPL interface MINTO Command Line Option MINTO AMPL Option e branching S deactivate all n3 loadnames m maxnodes t maxtime o output p preprocessing Table 2 MINTO AMPL Options 3 System design It is well known that problem specific knowledge can be used advantageously to increase the performance of the basic linear programming branch and bound algorithm for mixed integer programming MINTO 2Currently only the Linux OsiClp MINTO solver comes with this feature attempts to use problem specific knowledge on two levels to strengthen the LP relaxation to obtain better feasible solutions and to improve branching At the first level system functions use general structures and at the second level application f
34. Lud xx t n n Update Update Fathom I Fathom Fe Ede ap E Ooh jp 7 AA e quc d n Zip gt Z best ModifyBounds E EG L DeleteCons Do GenerateCons n GenerateCons di Feasible gt p n 4 P M Success Zprim gt Zbest PrimalHeuristic Update a Y us lt Success gt Fathom i TERS JJ Branch LA GM Ko Figure 2 The underlying algorithm 10 qn appl delvariables t lt appl terminatelp gt a I eJ gr appl_feasible gt te appl_fathom AAA E a OA appl fathom aa Kc umi x zi appl delconstraint d S 4 ppl_terminatenod e 5 appl constraints IS L a 4 ES P appl feasible gt A cia EE ES appl_fathom E al 5d appl divide 7 11 CI aes Figure 3 The application functions class constraint MIXUB jer jt jeruc 64 lt ao MIXEQ jeB jTi 2 jeruc 44 ao NOBINUB Y jeruc 4313 lt ao NOBINEQ jere 4313 ag ALLBINUB are Ajj lt ao ALLBINEQ D jer 474 ao SUMVARUB 2 ef ver YY My lt 0 SUMVAREQ ya ver 8797 Aj ty 0 VARUB jyj Ap Tp L 0 VAREO AjYj axtx 0 VARLB AjYj ALT gt 0 BINSUMVARUB Deza 4 apt lt 0 BINSUMVAREQ 2 EBA ajtj axtx 0 BINSUMIVARUB 2 jeBVik Lj
35. activate or delete global constraints and MINTO may rearrange global and local constraints To provide an easy and fail safe mechanism for retrieving information about certain constraints MINTO provides a names mode When MINTO is invoked with names mode active each of the con straints generated by the application has to be given a unique name Afterwards the index of a con straint can be retrieved with one of two utility functions Ip cix and minto cix Both functions require a name as parameter and return an index For example the slack of a constraint with name cname can be retrieved by Ip slack Ip cix cname and information on a constraint with name cname can be retrieved by inq cons minto cix cname A similar mechanism is provide for retrieving information about variables 5 4 1 lp vix This function returns the index of the variable with the specified name in the active formulation If the name does not exist the return value will be ERROR if the variable is inactive the return value will be DEACTIVATED PARAMETERS vname A character pointer to the name of the variable 5 4 2 minto vix This function returns the index of the variable with the specified name in the current formulation If the name does not exist the return value will be ERROR PARAMETERS vname A character pointer to the name of the variable 5 4 3 lp cix This function returns the index of the constraint with the specified name in the active formulati
36. and update its internal administration set_var This function signals that the application program has changed the contents of the info_var variable and that MINTO should get the data of the variable and update its internal administration MINTO only accepts changes of the bounds of a variable PARAMETERS index An integer containing the index of the variable set_obj This function signals that the application program has changed the contents of the info_obj variable and that MINTO should get the data of the variable and update its internal administration set_constr This function signals that the application program has changed the contents of the info_constr variable and that MINTO should get the data of the variable and update its internal administration MINTO only accepts changes of the coefficients and the status If the status is changed to DELETE the constraint will be removed from the original formulation PARAMETERS index An integer containing the index of the constraint 29 For internal reasons the preprocessing at the start of the evaluation of a node of the search tree is limited to changing bounds on variables The following example shows how appl preprocessing can be used to identify and delete redundant rows from the original formulation E_PREP C tinclude lt stdio h gt include minto h appl_preprocessing unsigned appl_preprocessing id int id identification of active minto
37. ar vname array for names of vars added int sdim length of small arrays int ldim length of large arrays int j int col_nz int col_ind double col_coeff int col_class double col_obj double col 1b double col ub inq form 33 col_ind int calloc info_form form_ccnt sizeof int col_coeff double calloc info_form form_ccnt sizeof double vcnt 0 nzcnt 0 while get column amp col_nz amp col class col ind col_coeff amp col obj amp col_lb amp col ub if nzcnt col nz gt ldim continue vfirst vcnt nzcnt vclass vcnt col class vobj vcnt 7 col obj varlb vcnt col lb varub vcnt col ub for j 0 j lt col nz j 4 vind x nzcnt col ind jl vcoef nzcnt col coeff jl if vcnt sdim break vfirst vcnt nzcnt free col_ind free col_coef return vcnt gt 0 SUCCESS FAILURE unsigned get_column col_nz col_class col_ind col_coeff col obj col lb col ub int col nz int col class int col ind double col coeff double col obj double col 1b double col ub 1 This function tries to generate a column It returns 1 if it successful and O otherwise 34 6 8 appl delvariables THIS FUNCTION IS NOT IMPLEMENTED IN MINTO V3 1 IF YOU REQUIRE THIS FUNCTIONALITY CONTACT THE CODE MAINTAINERS This function allows the application to delete on
38. ar in the arrays adjnodes and edges extern int adjnodes extern int adjedges appl_primal unsigned appl_primal id zlp xlp intlp zprimal xprimal zpnew xpnew xpstat int id identification of active minto double zlp value of the LP solution double xlp values of the variables int intlp integrality status of LP solution double zprimal value of the primal solution double xprimal values of the variables double zpnew variable for new value of lower bound double xpnew array for new values of the variables int xpstat variable for status of associated solution register int j k int ix int mark double maxxlp if intlp TRUE return FALSE xpstat TRUE zpnew 0 0 ing_form 37 inq obj O mark int calloc info form form vcnt sizeof int for 35 I ix UNDEFINED maxxlp 0 0 for j 0 j lt info form form vent j if mark j FREE if xlp j gt maxxlp I maxxlp xlp jl ix j if ix UNDEFINED break else mark ix FIXED xpnew ix 1 0 zpnew info_obj obj_coef ix for k adjnodes ix k lt adjnodes ix 1 k I mark adjedges k FIXED xpnew adjedges k 0 0 free mark return SUCCESS 6 11 appl feasible This function allows the application to verify that a solution to the active formulation satisfying the integrality con
39. associated bound VLB typedef struct int vub_var index of associated 0 1 variable double vub_val value of associated bound VUB Due to MINTO s philosophy to use as few functions as possible from the LP solver and MINTO s row oriented internal data structures retrieving the column associated with a variable may be very time consuming Furthermore in many cases an application uses inq var only to obtain information on the bounds or the type of a variable In such situations there is no need to retrieve the column associated with the variable Therefore we have introduced the boolean colinfo to indicate whether or not the column associated with the variable should be retrieved Setting colinfo to NO may result in an increased 15 performance of an application The following example shows how inq_var can be used to print the variables that are fixed in the current formulation E FIXED C tinclude lt stdio h gt include minto h WriteFixed void WriteFixed O 1 int j for inq form O j 0 j lt info form form vent j 4 inq var j NO if info var var lb gt info var var ub EPS 4 printf Variable d is fixed at f n j info var var lb 5 1 3 inq obj This function retrieves the number of variables that appear in the objective function with a nonzero coefficient and for each of these variables the index of the variable and the nonzero coefficient The same
40. bades ae a er sea Do URS Skl gt CC PCI E RR ARES GE ens ADS MINO VIX 4 e soo oe e RS omoes e a A at UR PP Rees 5 243 Ip it 2 o gue ue sr Reese E Age sa med Bleed es ETG Sees 5 4 4 aminto CIX A ks Tox ee EE Keke Res Process Statistics at RR gute re ew d LA sake Woo 5 5 l statevnds sus rr Kand de PG A A E wa Se e Ee toU 5 5 2 Stat maxnds og dox x Remi Soe are ab YN Tot eR Ee RR ERROR 5 5 3 Stat Avnds o SR Eo RR RE LS SE WEE UR ERR GE EH 5 5 4 stat depth sooo te GE BEGGE CN RR ege 5 5 5 stat IpCnit x sau saken Selek gw we Done se RA OE ee reb e e yd 5 5 6 stat gap uxo ge le RR EE Eh ata ey adidas 5 5 7 Stat maxlprows 4 12g ass UR A tada ens 5 5 8 stat maxlpcols 4 vu sous RR Rd REA MRRUS E RI RR Ge 5 5 9 stat cliquecnt ii IR a AERE UP ee etg 5 5 10 stat implicationent le 5 5 11 stat knapcovent e E e e ee 5 5 12 stat gubcovent GAL i CG GL S CL A Og SA RE a RC har es 5 5 13 stat sknapcovcnt ia ORO a ic a atada 5 5 14 stat flowcovent viii a A gp de AUC Ue ee a e ARE 5 545 Stat time Suas E E Ok he PMS RECS Ge A ooo oo A 6 Application Functions 6 Minto e x AE EG A AAA EEA SEG 6 2 applmps i 4 um RR mde Roh P dedo Re aei ee ele 6 3 APPEAR uei as o oy donus 6 AE KN ede de inh ae avs 6 4 applinitlp an r A ase G ka Baa Ser d eee veut 6 5 appl preprocessing e rs 6 6 appl nodes o See Sa Kam GK TEGER Se uy a a Sp faic 6 7 ppl variables 24 le a
41. ction returns the number of constraints in the active formulation i e the number of constraints currently loaded in the LP solver 5 3 3 Ip slack This function returns the slack or surplus of the constraint If the index is invalid or the associated con straint is inactive the return value will be INE PARAMETERS index An integer containing the index of the constraint 5 3 4 Ippi This function returns the dual value of the constraint If the index is invalid or the associated constraint is inactive the return value will be INE PARAMETERS index An integer containing the index of the constraint 5 3 5 lprc This function returns the reduced cost of the variable If the index is invalid the return value will be INE PARAMETERS index An integer containing the index of the variable 19 5 3 6 lp base This function retrieves the status of each variable i e BASIC ATLOWER ATUPPER or NONBASIC and each constraint i e CBASIC or CNONBASIC A call to Ip base initializes the variable info base that has the following structure typedef struct info base int base vstat array with the status of each variable int base cstat array with the status of each constraint INFO BASE 5 4 Names mode Applications generating constraints either in appl constraints or appl divide may have a difficult time keeping track of the indices of these constraints MINTO may generate system inequalities MINTO may de
42. d int id identification of active minto int vcnt variable for number of variables to be deleted int vind array for indices of the variables to be deleted int j vcnt 0 for j 0 j lt Ip vent O j 35 if lp_rc j gt TOLERANCE 4 vind vent j return SUCCESS 6 9 appl terminatelp This function allows the application to terminate the solution of the current linear program without hav ing reached an optimal solution i e before all variables have been priced out It has to return either NO in which case MINTO assumes that the application wants to continue the solution of the current linear program and it therefore ignores the parameter zub or YES in which case MINTO assumes that the application wants to terminate the solution of the current linear program and that an alternative upper bound is provided through the parameter zub If zub is set to INE MINTO assumes that the active problem is infeasible and that the node can be fathomed PARAMETERS id An integer containing the identification of the active MINTO copy zlp A double containing the value of the LP solution xlp An array of doubles containing the values of the variables zub A double to hold the alternative upper bound 6 10 appl primal This function allows the application to provide MINTO with a lower bound and possibly an associated primal solution It has to return either FAILURE in which case MINTO assume
43. d up of its value in the current LP solution Note that if the integer variable is binary this corresponds to fixing the variable to zero and one respectively Each node of the branch and bound tree also receives a unique identification This identification consists of two numbers depth and creation Depth refers to the level of the node in the branch and bound tree Creation refers to the total number of nodes that have been created in the branch and bound process The root node receives identification 0 1 The two following examples show how appl divide can be used to implement the default branching scheme In the first example the variable is fixed by specifying new bounds In the second example the variable is fixed by specifying new constraints E DIVIDE C include lt stdio h gt include lt math h gt include minto h appl divide unsigned appl divide id depth creation zlp xlp zprimal xprimal nent vent vind vtype vvalue nzcnt ccnt cfirst cind ccoef csense crhs cname bdim sdim ldim int id identification of active minto long depth identification depth long creation identification creation double zlp value of the LP solution double xlp values of the variables double zprimal value of the primal solution double xprimal values of the variables int ncnt variable for number of nodes int vcnt array for number o
44. diff xlp INDEX i j xlp INDEX j k xlp INDEX k i 2 if diff gt EPS return NO return YES 6 12 appl fathom This function allows the application to provide an optimality tolerance to terminate or prevent the pro cessing of a node of the branch and bound tree even when the upper bound value associated with the node is greater than the value of the primal solution It has to return either FAILURE in which case 39 MINTO assumes that further processing of the node is still required or SUCCESS in which case MINTO assumes that further processing of the node is no longer required For an active node processing is ter minated for an unevaluated node MINTO deletes it from the list of nodes to be processed PARAMETERS id An integer containing the identification of the active MINTO copy zlp A double containing the value of the LP solution zprimal A double containing the value of the primal solution The following two examples show how the function appl fathom can be used to implement optimality tolerances The first example shows how to incorporate the fact that objective coefficients are all inte ger The second example shows how to build a truncated branch and bound algorithm that generates a solution that is within a certain percentage of optimality E_FATHOM C include lt stdio h gt include minto h appl fathom unsigned appl fathom id zlp zprimal int id identificati
45. ditions does indeed constitute a feasible solution It has to return either YES in which case MINTO assumes that the solution is feasible and therefore terminates processing this node or NO in which case MINTO assumes that the solution is not feasible and therefore continues processing this node PARAMETERS id An integer containing the identification of the active MINTO copy zlp A double containing the value of the LP solution xlp An array of doubles containing the values of the variables The following example shows how appl feasible can be used to accommodate partial formulations In 38 the linear ordering problem one usually deals with the 3 cycle inequalities 5 jx Ok lt 2 implicitly i e they may be generated only when they violate an LP solution The following code assumes the set of variables is 6 for i j 1 n i j and verifies whether the given solution is feasible or not E_FEAS C include lt stdio h gt include minto h define INDEX I J CI n 1 AG lt 0 GJ J 1 appl feasible unsigned appl feasible id zlp xlp int id identification of active minto double zlp value of the LP solution double xlp values of the variables int i j k n double diff ing_form n info_form form_vcnt for i 0 i lt n i I for j 0 j lt n j for k 0 k lt n k if i j amp amp i k amp amp j k t
46. e of the linear programs by managing active constraints To be as flexible and powerful as possible when used to build a special purpose mixed integer optimizer MINTO provides various mechanisms for incorporating problem specific knowledge Finally to make future algorithmic developments easy to incorporate MINTO s design is highly modular This document focuses on the mechanisms for incorporating problem structure and only contains a minimal description of the general purpose techniques mentioned above The mechanisms for incorporating problem structure and customizing MINTO are discussed in Sec tions 5 6 7 8 and 9 under information application control bypass and miscellaneous functions Section 2 explains how to run MINTO and Sections 3 and 4 present the overall system design and a brief description of the system functions Section 10 discusses the development of applications that call MINTO recursively Sections 11 12 13 and 14 discuss environment variables direct access to the lin ear program programming considerations and computational results Finally Section 15 contains some remarks on availability and future releases Release 3 1 of MINTO was prompted by the porting of MINTO to more recent versions of the CPLEX LP solver a port to use the COIN OR OsiSolverInterface which allows the use of 11 different LP solvers to be used with MINTO and of the creation and packaging of an AMPL interface to MINTO 2 Using MINTO In this
47. e or more of the previously generated variables from the active formulation i e the formulation currently loaded in the LP solver It has to return either FAILURE in which case MINTO assumes that no variables have to be deleted and it therefore ignores the parameters vent and vind or SUCCESS in which case MINTO assumes that variables have to be deleted and that these variables are available through the parameters vent and vind PARAMETERS id An integer containing the identification of the active MINTO copy vent An integer to hold the number of variables to be deleted from the current formulation vind An array of integers to hold the indices of the variables to be deleted from the current formulation Note that variables are deleted from the active formulation Therefore indices are considered to be rela tive to the active formulation Note also that it is only possible to delete previously generated variables either by MINTO or by the application It is not possible to delete variables from the initial formulation The following example shows how appl delvariables can be used to examine all active variables and delete all variables whose reduced cost is greater than a certain tolerance MINTO will ignore all indices referring to variables from the initial formulation E DELVARS C tinclude lt stdio h gt include minto h define TOLERANCE 100 appl_delvariables unsigned appl delvariables id vcnt vin
48. ecifying the type of simplex algorithm i e PRIMAL DUAL BARRIER BARRI ERCROSS HYBNETWORKPRIMAL or HYBNETWORKDUAL Note that in the default setting MINTO solves the first linear program with the primal simplex method and all subsequent linear programs with the dual simplex method The first barrier method BARRIER does not perform a cross over at the end and therefore does not terminate with a basic solution The second barrier method BARRIERCROSS does perform a cross over at the end and therefore terminates with a basic solution The hybrid network methods extract an embedded network call the network optimizer to obtain an optimal basis to the network and then optimize the entire linear program using a primal HYBNETWORKPRIMAL or dual HYBNETWORKDUAL simplex method 7 4 ctrlippresolve This function indicates whether the presolver embedded in the LP solver should be activated or deacti vated 3These methods are only available for CPLEX based versions of MINTO 56 PARAMETERS CPLEX selector An integer specifying whether to activate or to deactivate the LP presolver i e PRESOIVE or NOPRESOLVE Note that in the default setting of MINTO the presolver embedded in the LP solver is not activated 7 5 ctrl Ippricing This function selects the pricing algorithm that is used to solve the active formulation PARAMETERS CPLEX algorithm An integer specifying the type of simplex algorithm i e PRIMAL or DUAL selector
49. ert the constraint status into a printable string char ConvertStatus status int status switch status I case ACTIVE return act 71 case INACTIVE return inact case DELETED return del 72
50. f variables int vind array for indices of variables char vtype array for type of bounds double vvalue array for value of bounds int nzcnt variable for number of nonzero coefficients int ccnt array for number of constraints int cfirst array for positions of first nonzero coefficients int cind array for indices of nonzero coefficients double ccoef array for values of nonzero coefficients char csense array for senses double crhs array for right hand sides char cname array for names 49 int bdim size of bounds arrays int sdim size of small arrays int ldim size of large arrays register int i register double frac diff int index 1 double mindiff double 1 for ing_form i 0 i lt info_form form_vcnt i I if inq var i NO info var var class CONTINUOUS frac xlp i floor xlplil if frac gt EPS amp amp frac lt 1 EPS I diff fabs frac 0 5 if diff lt mindiff mindiff diff index i ncnt 2 vent 0 vent 1 vind 0 index vtype 0 U vvalue 0 double 0 vind 1 index vtype 1 L vvalue 1 double 1 ccnt 0 0 ccnt 1 0 return SUCCESS E DIVIDE C include lt stdio h gt include lt math h gt 50 include minto appl divide unsigned h appl divide id depth crea
51. ged eee kresne s dd se Ses PG MEE 6 8 appldelvariables ee ee ee ee ee ee eis 6 9 applterminatelp 2er o O appL primal cnica cake iR Bee le e wl dv doe ee a eS 6 1 L appl feasible u oe aut Gn te Gee RE Bd aa see ode tee eet 6 12 appl fathom une a s ke steere ee eA p e mte Aanby 6 13 appl bo nds oa pa re TT ES EAT Sor E se sek Re E Mk Gaga NE GE 6 14 applconstraints i e e zl hoe sed Gas sea AGE E RR US 6 15 appl delconstraints arver ee 6 16 appl terminatenode v vr rv rv vnr nrk ee ee ee ee eis 6 17 lt applidivide x iaa a aaa VE A a 6 8 applrank ii A AAA A RA YS 6 19 appl exit iS ER a A AA a RR 6 20 ppl quit Lt RE EEE SR A tt da o 7 Control Functions 7 1 MINTO Algorithm Control Functions leen 7 1 1 etri clique coi 8 ah ras ARES Oe eRe 7 1 2 ctrlimplication eer 71 3 ctrl knapcov o seu om RW RR dox A e tee Ene RETE 7 1 4 ctrlflowCOov nck s e ges a aer goh AU cg A a STER TIS Ctr output i cue USE Se as ES UNE rA RUE RAM 7 2 Linear Programming Control Functions a a 7 3 etrlipmethod sje ree IA Ge Ice ear AA p RE le 74 ctrllppresolve oir sg ces ooo xw SR RE ovatum Ee ee SE og 7 5 ctrl Ippricinig i532 ees bere Id Ge ah ery FR RR Bb RUP NUS Lb donet 4776305 7 6 etrlippricinglist ar ore Rep e mure RR due ds me d de RR RIT 7 7 ctrl lpperturbeonst 4 7 8 ctrl lpperturbmeth
52. generation routines better primal heuristics and different strategies for getting upper bounds such as Lagrangian relaxation See the website http coral ie lehigh edu minto for the most up to date releases 64 References 1 2 3 4 5 6 7 8 9 G L NEMHAUSER M W P SAVELSBERGH G C SIGISMONDI 1994 MINTO a Mixed INTeger Opti mizer Oper Res Letters 15 48 59 M W P SAVELSBERGH 1994 Preprocessing and Probing for Mixed Integer Programming Problems ORSA J Comput 6 445 454 Z GU G L NEMHAUSER M W P SAVELSBERGH 1998 Cover Inequalities for 0 1 Linear Programs Computation INFORMS Journal on Computing 10 427 437 Z GU G L NEMHAUSER M W P SAVELSBERGH 1996 Cover Inequalities for 0 1 Linear Programs Complexity INFORMS J Comput to appear Z GU G L NEMHAUSER M W P SAVELSBERGH 2000 Sequence Independent Lifting Journal of Combinatorial Optimization 4 109 129 Z GU G L NEMHAUSER M W P SAVELSBERGH 1999 Lifted Flow Cover Inequalities for Mixed 0 1 Integer Programs Mathematical Programming 85 439 467 J LINDEROTH M W P SAVELSBERGH 1999 A Computational Study of Search Strategies in Mixed Integer Programming INFORMS Journal on Computing 11 173 187 A ATAMTURK G L NEMHAUSER M W P SAVELSBERGH 1998 Conflict Graphs in Integer Program ming European Journal of Operational Research 121 40 55 R FOURER D M GAY AND B W KERNIGHAN 2
53. h constraint 5 1 1 inq form This function retrieves the number of variables and the number of constraints of the current formulation A call to inq form initializes the variable info form that has the following structure typedef struct info form 1 int form vcnt number of variables in the formulation int form ccnt number of constraints in the formulation INFO FORM The following example shows how ing form can be used to print the size of the current formulation E SIZE C include lt stdio h gt include minto h WriteSize void WriteSize ing_form printf Number of variables din info_form form_vcnt printf Number of constraints d n info_form form_ccnt 5 1 2 ing var This function retrieves the variable name variable class the objective function coefficient the number of constraints in which the variable appears with a nonzero coefficient and for each of these constraints the index of the constraint and the nonzero coefficient the status of the variable the lower and upper bound 14 associated with the variable additional information on the bounds of the variable and if the variable type is continuous and the variable appears in a variable lower or upper bound constraint the index of the associated binary variable and the associated bound Variable class is one of CONTINUOUS INTEGER and BINARY Variable status is one of ACTIVE INACTIVE or DEL
54. he application It is not possible to delete constraints from the initial formulation The following example shows how appl delconstraints can be used to examine all active constraints every tenth iteration and delete all the constraints whose slack is greater than a certain TOLERANCE MINTO will ignore all indices referring to constraints from the initial formulation E_DELCONS C include lt stdio h gt include minto h define TOLERANCE 0 1 static int lpcounter 0 appl_delconstraints unsigned appl_delconstraints id ccnt cind int id identification of active minto int ccnt variable for number of constraints to be deleted int cind array for indices of the constraints to be deleted int i if lpcounter 10 0 1 return FAILURE else ccnt 0 for i 0 i lt Ip cent O i if lp slack i lt TOLERANCE lp_slack i gt TOLERANCE cind ccnt i return ccnt gt 0 SUCCESS FAILURE 46 6 16 appl terminatenode This function allows the application to take over control of tailing off detection and set the threshold value used by MINTO to detect tailing off It has to return either NO in which case MINTO assumes that the application does not want to replace the default value of the threshold by its own and it therefore ignores the parameter threshold or YES in which case MINTO assumes that the application wants to replace
55. he max imum amount of memory in use at any time but it also increases the running time experiments have indicated a moderate increase of about 3 5 percent MIOROWSZ MIOCOLSZ MIONZSZ MIOCHARSZ For efficiency CPLEX requires that the memory nec essary to store the active constraint matrix at any moment during the solution process is allocated at the start of the solution process i e memory for the initial constraint matrix as well as memory for rows and columns that may be added during the solution process Once this memory has been allocated it cannot be changed As MINTO supports branch and cut and branch and price algorithms it allocates besides the memory necessary to store the initial constraint matrix memory for MIOROWSZ and MIO COLSZ extra rows and columns MIONZSZ extra nonzero coefficients and MIOCHARSZ extra row and column name characters These default sizes can be changed by setting the corresponding environment variables For example if no columns will be generated then MIOCOLSZ can be set to zero Do not set MIOCHARSZ to zero even if no names are associated with rows and columns because CPLEX always stores the string termination character 10 Default values are MIOROWSZ 16184 MIOCOLSZ 16184 MIONZSZ 311296 and MIOCHARSZ 65536 MIOCUTPOOLSZ MIOCUTDELBND To control the size of the active formulation MINTO monitors the dual variables associated with all the global constraints that have been generated during the solution
56. information can be obtained by successive calls to ing var however using ing obj is much more efficient A call to inq_objQ initializes the variable info_obj that has the following structure typedef struct 1 int obj nz number of variables with nonzero coefficients int obj ind indices of variables with nonzero coefficients double obj coef actual coefficients INFO 0BJ The following example shows how inq obj can be used to print the variables with a nonzero objective coefficient E OBJ C 16 tinclude lt stdio h gt include minto h Write0bj void Write0bj int j inq obj O for j 0 j lt info obj obj nz j I printf Variable d has objective coefficient f n info obj obj ind jl info obj obj coef j F 5 1 4 inq constr This function retrieves the constraint name constraint class the number of variables that appear in the constraint with a nonzero coefficient and for each of these variables the index of the variable and the nonzero coefficient the sense of the constraint the right hand side of the constraint the status of the constraint the type of the constraint and additional information on the constraint Constraint class is one of MIXUB MIXEQ NOBINARYUB NOBINARYEQ ALLBINARYUB ALLBINA RYEQ SUMVARUB SUMVAREQ VARUB VAREQ VARLB BINSUMVARUB BINSUMVAREQ BINSUMIVARUB BINSUM1VAREQ BINSUM1UB or BINSUM1EQ Constraint status is one of
57. ixed integer program directly within MINTO using the application function appl_mps see Section 6 2 However even in that case MINTO requires a name to be specified on the command line MINTO always opens a file lt name gt log to write out information that may be useful to determine the cause of a premature exit in case this occurs Furthermore this name will be used as the problem name which would otherwise have been specified in the MPS file The run time behavior of MINTO depends on the command line options The meanings of the various command line options are given in Table 1 The command line options allow the user to deactivate selectively one or more system functions and to specify the amount of output desired MINTO assumes that the mixed integer program that has to be solved represents a minimization problem unless the x command line option is specified in which case MINTO assumes it represents a maximization problem Regardless of whether MINTO has found an optimal solution or not it will abort after evaluating 1 000 000 nodes The m lt gt command line option can be used to change the maximum number of nodes to be evaluated Regardless of whether MINTO has found an optimal solution or not it will abort after 1 000 000 cpu seconds The t lt gt command line option can be used to change the maximum cpu time In default mode MINTO produces very little output The o lt 0 1 2 3 gt command line option can be used to
58. n problem If the original formulation describes a minimization problem MINTO will change the signs of all the objective function coefficients As a consequence one has to be careful when interpreting values such as the reduced cost of a variable MINTO only stores the nonzero coefficients of variables and constraints Therefore a set of variables can and will always be specified by three arrays vfirst vind vcoef Vind and vcoef contain the indices and values of nonzero coefficients respectively Vfirst i indicates the position of the first nonzero coefficient of the ith variable in the arrays vind and vcoef vfirst i 1 indicates the first position after the last nonzero coefficient of the ith variable in the arrays vind and vcoef Note that this implies that if a set of k variables is specified vfirst k has to be defined Similarly a set of constraints can and will always be specified by three arrays cfirst cind ccoef Cind and ccoef contain the indices and values of nonzero coefficients respectively Cfirst indicates the position of the first nonzero coefficient of the ith constraint in the arrays cind and ccoef cfirst i 1 indicates the first position after the last nonzero coefficient of the th constraint in the arrays cind and ccoef Note that this implies that if a set of k constraints is specified then cfirst k has to be defined 22 6 1 minto This function invokes MINTO and takes as arguments the problem name and a stri
59. near ordering problem E CONS C include lt stdio h gt include minto h define INDEX I J C I n 1 AQ lt 0 CD J 1 appl constraints unsigned appl constraints id zlp xlp zprimal xprimal nzcnt ccnt cfirst cind ccoef csense crhs ctype cname sdim ldim int id identification of active minto double zlp value of the LP solution double xlp values of the variables double zprimal value of the primal solution double xprimal values of the variables int nzcnt variable for number of nonzero coefficients int ccnt variable for number of constraints int cfirst array for positions of first nonzero coefficients int cind array for indices of nonzero coefficients double ccoef array for values of nonzero coefficients char csense array for senses double crhs array for right hand sides int ctype array for the constraint types LOCAL or GLOBAL int cname array for the names int sdim length of small arrays int ldim length of large arrays 44 int i j k n double diff ccnt 0 nzcnt 0 ing_form n info_form form_vcnt for i 0 i lt n i I for j 0 j lt n j 4 for k 0 k lt n k if i j amp amp i k amp amp j k 1 diff xlp INDEX i j xlp INDEX j k xlp INDEX k i 2 if diff gt EPS
60. ng with run time op tions For a description of the run time options see Section 2 PARAMETERS name A string containing the problem name options A string containing the run time options When MINTO finishes it stores the optimal solution in a variable info opt that has the following structure typedef struct info opt 4 int opt stat exit status optimal time or node limit quit double opt value value of optimal solution int opt nzcnt number of nonzero s in optimal solution int opt ix indices of nonzero s in optimal solution double opt val values of nonzero s in optimal solution INFO OPT Similar to the inquiry functions the calling program can access the optimal solution by inspecting the fields of the variable The following example shows how to call MINTO and print the optimal solution MINTO C include lt stdio h gt include minto h Minto void main int i Solve the mixed integer program specified in example mps which is a maximization problem and provide extensive output minto example x 03 Write out the optimal solution ourselves 23 printf Optimal value f n info opt opt value for i 0 i lt info opt opt nzcnt i I printf Value d f n info opt opt ix i info opt opt vallil 6 2 appl mps This function allows the application to initialize the original formula
61. ntf stderr Unable to open EXAMPLE LOG n return STOP fprintf fp log Solving problem s with MINTO n inq prob O return CONTINUE 6 4 appl initlp This function provides the application with an entry point in the program to indicate whether column generation will be used for the solution of the linear programming relaxations MINTO ignores the return value PARAMETERS id An integer containing the identification of the active MINTO copy colgen An integer to indicate whether column generation will be used i e TRUE of FALSE MINTO solves the initial linear program using a primal simplex method and all subsequent linear pro grams using a dual simplex method One reason for using the dual simplex method is that the dual simplex method approaches the optimal value of the linear program from above and thus provides a valid upper bound at every iteration not only on the linear programming solution but also on the mixed integer programming solution Therefore the solution of the linear program can be terminated as soon as this upper bound drops below the current lower bound because at that point the node can be fath omed by bounds However if the linear program is solved using column generation the values no longer provide valid upper bounds and the solution of the linear program cannot be terminated earlier It is for this reason that MINTO needs to know whether the linear programs are solved using column generation or not
62. od lees 7 9 etrlilprefactorfreq 30 A AA A ISO 8 Bypass functions B bypasslp e a eeoa ii RUE KR REUS DEE 8 2 bypassfathom err 8 3 bypass integral so sise nd ace goa m BC he a GE hk RIS 9 Miscellaneous Functions 91 WE Probe i euo oeste MESE UR es e Pat GSE ke AAN 10 Calling MINTO recursively 22 23 24 27 28 29 31 32 35 36 36 38 39 41 43 45 47 48 52 54 55 55 55 55 55 55 56 56 56 56 56 57 57 57 57 57 58 58 58 58 59 59 59 11 Direct access to the active LP NED ne 5 E ED DE dar ais dh nae E e E ee dod T2 OST 5 oa kes Sete ae A weet ee dy ide EB Sad Se Gre sere 12 Environment variables 13 Programming considerations 14 Availability and Future Releases 62 62 62 62 64 64 Functional description of MINTO a Mixed INTeger Optimizer Version 3 1 Martin W P Savelsbergh George L Nemhauser Georgia Institute of Technology School of Industrial and Systems Engineering Atlanta GA 30332 0205 USA Jeff T Linderoth Lehigh University Department of Industrial and Systems Engineering Bethlehem PA 18015 USA Abstract MINTO is a software system that solves mixed integer linear programs by a branch and bound algo rithm with linear programming relaxations It also provides automatic constraint classification prepro cessing primal heuristics and constraint generation Moreover the user can enrich the basic algorithm by providing a variety
63. of specialized application routines that can customize MINTO to achieve max imum efficiency for a problem class This user s manual documents MINTO by specifying what it is capable of doing and how to use it 1 Introduction MINTO Mixed INTeger Optimizer is a tool for solving mixed integer linear programming MIP prob lems of the form max 5 Cjtj 5 Cit 1 Cit jeB jel jec S agz V as 047 b i 1 m JEB jel jec O lt 2j lt 1 jEB leg vj lt usj JEIUC sj EL j BUI zj ER jec where B is the set of binary variables I is the set of integer variables C is the set of continuous variables the sense of a constraint can be gt or and the lower and upper bounds may be negative or positive infinity or any rational number A great variety of problems of resource allocation location distribution production scheduling reliability and design can be represented by MIP models One reason for this rich modeling capability is that various nonlinear and non convex optimization problems can be posed as MIP problems Although MILPs are difficult to solve in general the past ten years has seen a dramatic increase in both the quantity and quality of open source and noncommercial software designed to solve MILPs Noncom mercial software tools can provide a viable alternative for users who cannot afford the sometimes costly commercial offerings Open source software tools can also be more extensible and easier to customize
64. of the form So a3 Y yz 5 ojz lt Ci 14 Y y JEC1 JEC2 JEBNC JEC2 where C C U C5 with C4 4 a minimal set such that 7 jecaj gt ao Lifted GUB cover inequalities have the same form but are derived from a structure consisting of a single knapsack constraint and a set of non overlapping generalized upper bound constraints Generalized flow covers are derived from Y w W ao jeN jeN yj amp ajz jeN UN and are of the form X lytA at a ao A aA a M w JEC jec jeL JEN VLUC with C C C NT N a minimal set such that 5 05 jec 4j700 A gt 0and LE NT NCT After solving a linear program MINTO searches for non basic 0 1 variables whose values may be fixed according to the magnitude of their reduced price It also tries to find feasible solutions using recursive rounding of the optimal LP solution MINTO uses a hybrid branching scheme Under certain conditions it will branch on a clique constraint If not it chooses a variable to branch on based on a priority order it creates 5 Information Functions For the sequel it is assumed that the reader has a working knowledge of the C programming language 5 1 Current formulation Information about the current formulation can be obtained through the inquiry functions ing form inq obj inq constr and inq var and their associated global variables info form info obj info constr and info var Each of these inquiry functions updates its associated variable so
65. on vent An integer to hold the number of variables for which bounds have to be modified vind An array of integers to hold the indices of the variables for which bounds have to be modi fied vtype An array of characters to hold the types of modification to be performed i e lower bound Lor upper bound U vvalue An array of doubles to hold the new values for the bounds bdim An integer containing the length of the arrays vind vtype and vvalue The following example shows how appl bounds can be used to implement reduced cost fixing E BNDS C tinclude lt stdio h gt include minto h 41 appl_bounds unsigned appl bounds id zlp int id double zlp double xlp double zprimal double int vcnt int vind char vtype double vvalue int bdim 1 int j double lb vcnt 0 xprimal ub xlp zprimal xprimal vcnt vind vtype vvalue bdim identification of active minto value of the LP solution values of the variables value of the primal solution values of the variables variable for number of variables array for indices of variables array for type of bounds array for value of bounds size of arrays Retrieve basis information lp base Loop through all variables inq form 0 for j 0 j lt info_form form_vcnt j
66. on If the name does not exist the return value will be ERROR PARAMETERS cname A character pointer to the name of the constraint 20 5 4 4 minto cix This function returns the index of the constraint with the specified name in the current formulation If the name does not exist the return value will be ERROR PARAMETERS cname A character pointer to the name of the constraint 5 5 Process statistics When MINTO finishes it writes out some statistics on the solution process such as the number of evalu ated nodes the number of generated lifted knapsack cover inequalities and the elapsed cpu time The process solution statistics functions allow an application to monitor this information during the execution of the algorithm 5 5 1 stat evnds This function returns the number of evaluated nodes 5 5 2 stat maxnds This function returns the maximum number of nodes that has been in the list of unevaluated nodes 5 5 3 stat avnds This function returns the average number of nodes that has been in the list of unevaluated nodes 5 5 4 stat depth This function returns the maximum depth of the search tree 5 5 5 stat lpcnt This function returns the number of linear programs that has been solved 5 5 6 stat gap This function returns the integrality gap 5 5 7 stat maxlprows This function returns the maximum number of rows that has been in the active linear program 5 5 8 stat maxlpcols This function returns the
67. on of active minto double zlp value of the LP solution double zprimal value of the primal solution if zlp zprimal lt 1 EPS return SUCCESS else return FAILURE E FATHOM C include lt stdio h gt include minto h define TOLERANCE 1 05 40 appl fathom unsigned appl fathom id zlp zprimal int id identification of active minto double zlp value of the LP solution double zprimal value of the primal solution if zlp lt TOLERANCE zprimal EPS return SUCCESS jJ else return FAILURE 6 13 appl bounds This function allows the application to modify the bounds of one or more variables It has to return either FAILURE in which case MINTO assumes that no bounds have to be changed and it therefore ignores the parameters vent vind vtype and vvalue or SUCCESS in which case MINTO assumes that there are variables for which the bounds have to be changed and that the relevant information is available through the parameters vent vind vtype and vvalue PARAMETERS id An integer containing the identification of the active MINTO copy zlp A double containing the value of the LP solution xlp An array of doubles containing the values of the variables zprimal A double containing the value of the primal solution xprimal An array of doubles containing the values of the variables associated with the primal solu ti
68. probing 1 preprocessing and limited probing 2 and preprocessing and extensive probing 3 Probing although potentially very effective can be time very consuming especially for problems with many binary variables See references 2 and 8 for more details about the types of preprocessing operations performed in MINTO A branching scheme is specified by two rules a branching variable selection rule and a node selection rule In default mode MINTO uses its own adapative variable selection and node selection rules The e lt 0 1 2 3 4 5 gt command line option can be used to specify a branching variable selection rule There are six variable branching selection rules maximum infeasibility 0 penalty based 1 strong branching 2 pseudocost based 3 adaptive 4 and SOS branching 5 The E lt 0 1 2 3 4 gt command line option can be used to specify a node selection rule There are five node selection rules best bound 0 depth first 1 best projection 2 best estimate 3 and adaptive 4 See reference 7 for more description of these branching and node selection rules MINTO attempts to generates cuts to improve the formulation during the evaluation of a node As a consequence there is a risk of tailing off Therefore MINTO monitors the progress resulting form cut generation If the amount of progress does not warrant cut generation anymore MINTO forces branching The B lt 0 1 2 gt command line option can be used to
69. rray of doubles containing the values of the variables associated with the primal solu tion The following example shows how appl_node can be used to implement a simple stopping rule E_NODE C include lt stdio h gt include minto h define GAPSIZE 0 5 extern FILE fp_log appl node unsigned appl node id depth creation zprimal xprimal int id identification of active minto int depth node identification depth int creation node identification creation double zprimal value of primal solution double xprimal value of the variables double gap stat_gap 31 if gap lt GAPSIZE fprintf fp log Terminated as gap Af is smaller than f n gap GAPSIZE return STOP else fprintf fp log Evaluating node 1d 1d n depth creation return CONTINUE 6 7 applvariables This function allows the application to generate one or more additional variables It has to return either FAILURE in which case MINTO assumes that no additional variables were found or no attempt was made to generate any and it therefore ignores the parameters nzcnt vent vobj vlb vub vfirst vind and vcoef or SUCCESS in which case MINTO assumes that additional variables have been found by the application and that they are available through the parameters nzcnt vcnt vobj vlb vub vfirst vind and vcoef PARAMETERS id zlp xlp zprimal xprimal
70. s of the constraints int vfirst starting positions of the columns of the variables int vind indices of the nonzero coefficients double vcoef nonzero coefficients int vstorsz total number of characters in the names of the variables char vstore names of the variables char vname starting positions of the names of the variables int cstorsz total number of characters in the names of the constraints char cstore names of the constraints char cname starting positions of the names of the constraints int i j double vobj double vlb 25 double vub char vtype char csense double crhs int vfirst int vind double vcoef char vstore char vname char cstore char cname vcnt SIZE ccnt SIZE nzcnt SIZE vobj double calloc _vlb double calloc _vub double calloc _vtype char calloc _csense char calloc _crhs double calloc _vfirst int calloc _vind int calloc _vcoef double calloc for _vfirst 0 0 j 0 _vobj j 1 0 v1b jl 0 0 vub jl 1 0 vtypeljl UB _vfirst j 1 j 1 vind j Js _vcoef j 1 0 vcnt sizeof vcnt sizeof vcnt sizeof vcnt sizeof ccnt ccnt sizeof sizeof double double double char char double vcnt i sizeof int nzcnt sizeof int
71. s that no lower bound was found by the application or no attempt was made to find one and it therefore ignores the parameters zp new xpnew and xpstat or SUCCESS in which case MINTO assumes that a lower bound has been found by the application and that it is available through the parameter zpnew and that an associated primal solution is available through the parameter xpnew if xpstat is set to TRUE PARAMETERS id An integer containing the identification of the active MINTO copy zlp A double containing the value of the LP solution xlp An array of doubles containing the values of the variables intlp An integer that indicates whether the LP solution is integral i e TRUE or FALSE zprimal A double containing the value of the current primal solution xprimal An array of doubles containing the values of the variables associated with the current primal solution zpnew A double to hold the value of the new primal solution xpnew An array of doubles to hold the values of the variables associated with the new primal solution xpstat An integer to indicate the existence of a solution vector i e TRUE or FALSE The following example shows how appl primal can be used to provide feasible solutions given a frac tional LP solution of a node packing problem 36 E PRIMAL C include lt stdio h gt include minto h define UNDEFINED 1 define FREE 0 define FIXED 1 The graph is represented as a forward st
72. separation problem f n info opt opt value for i 0 i lt info opt opt nzcnt i I printf Value A d fNn info opt opt ix i info opt opt vallil The remainder of the code should interpret the solution and if appropriate convert it to a violated inequality that can then be passed back to MINTO break case 1 break default printf ERROR in appl constraints id gt 1 Wn exit 1 return CONTINUE 61 11 Direct access to the active LP 11 1 CPLEX When MINTO is used in cooperation with the CPLEX linear optimizer direct acces to the active LP is provided through pointers mintoenv of type CPXENVptr and mintolp of type CPXLPptr This feature adds a lot of flexibility but should be handled with extreme care because direct changes to the CPLEX database are not reflected in MINTO s internal administration If at all possible the application program mer is advised to make changes using the functions provided by MINTO The following example shows how to obtain the number of variables and constraints in the active linear program directly from CPLEX E LP C tinclude lt stdio h gt include minto h tinclude cplex h appl_node unsigned appl_node id depth creation zprimal xprimal ecnt gap int id identification of active minto int depth node identification depth int creation node identification creation
73. specify a forcing strategy There are three strategies no forcing at all 0 no forcing at the root but forcing at the other nodes 1 and forcing at all nodes 2 option mintoamp options output 2 preprocessing 0 maxtime 1800 option mintoamp options deactivate all 1 Figure 1 Setting MINTO Options Through AMPL In default mode MINTO does not associate names with variables and constraints The n lt 1 2 3 gt command line option can be used to indicate that an application does want to associate names with variables 1 constraints 2 or with both variables and constraints 3 In default mode MINTO does not load an advanced basis when it starts evaluating a new node but relies on the LP solver to determine a good starting basis In most cases this works very well State of the art LP solver keep the basis associated with the last solved LP and employ sophisticated techniques to convert it to a good starting basis for the current LP Furthermore loading an advanced basis usually results in refactorization operations by the LP solver which may take a substantial amount of time Finally it is not at all obvious what constitutes a good advanced basis if row or column generation techniques are applied in the solution process The a command line option can be used to activate the use of an advance basis In that case MINTO will use the basis associated with the last LP solved in the parent node to create an advanced basis 2 4 Using M
74. ssociated with the primal solu tion nzent An integer to hold the number of nonzero coefficients to be added to the current formulation cent An integer to hold the number of constraints to be added to the current formulation cfirst An array of integers to hold the positions of the first nonzero coefficients of the constraints to be added cind An array of integers to hold the indices of the nonzero coefficients of the constraints to be added ccoef An array of doubles to hold the values of the nonzero coefficients of the constraints to be added 43 csense An array of characters to hold the senses of the constraints to be added crhs An array of doubles to hold the right hand sides of the constraints to be added ctype An array of integers to hold the types of the constraints to be added i e GLOBAL or LOCAL cname An array of character pointers to hold the names of the constraints to be added sdim An integer containing the length of the arrays cfirst csense crhs and ctype ldim An integer containing the length of the arrays cind and ccoef For reasons having to do with memory management the application has to allocate the memory using calloc to hold the name associated with a constraint MINTO will free that memory after it has installed the name in its internal administration The following example shows how appl constraints can be used to develop a branch and cut algorithm based on 3 cycle inequalities for the li
75. t i I if inq var i NO info var var class CONTINUOUS frac xlp i floor xlplil if frac gt EPS amp amp frac lt 1 EPS 4 dif if f fabs frac 0 5 diff lt mindiff I mindiff diff index i 51 ncnt 2 vent 0 0 vcnt 1 0 nzcnt 2 ccnt 0 1 ccnt 1 1 cfirst 0 0 cind 0 index ccoef 0 double 1 csense 0 L crhs 0 double 0 cfirst 1 1 cind 1 index ccoef 1 double 1 csense 1 G crhs 1 double 1 cfirst 2 2 return SUCCESS 6 18 appl rank This function allows the application to specify the order in which the nodes of the branch and bound tree are evaluated It has to return either FAILURE in which case MINTO assumes that the application wants to use the default rank function and it therefore ignores the parameter rank or SUCCESS in which case MINTO assumes that the rank for the current node is available through the parameter rank or REORDER in which case MINTO assumes that the application has switched to a different rank function In this case MINTO reorders the list of unevaluated nodes Before reordering each node receives a new rank by successive calls to appl rank PARAMETERS id An integer containing the identification of the active MINTO copy depth A long containing the depth in the branch and bound tree of the node that has been selected for evaluation creation A long con
76. t info form form vent j i fprintf fp log x d 4fNn j xopt j 54 fclose fp log return CONTINUE 6 20 appl quit This function provides the application with an entry point in the program to perform some final actions if execution is terminated by a lt ctrl gt C signal MINTO ignores the return value PARAMETERS id An integer containing the identification of the active MINTO copy zopt A double containing the value of the final solution xopt An array of doubles containing the values of the variables associated with the final solution If no solution vector exists the second parameter will be NULL 7 Control Functions MINTO provides more detailed control over the run time behavior of MINTO through a set of control functions Each of these control functions can be called any time during the solution process and activates or deactivates one of the system functions 7 1 MINTO Algorithm Control Functions 7 1 1 ctrl clique This function activates or deactivates generation of clique constraints PARAMETERS indicator An unsigned integer to hold a status indicator that controls the generation of clique con straints i e ON or OFE 7 1 2 ctrl implication This function activates or deactivates generation of implication constraints PARAMETERS indicator An unsigned integer to hold a status indicator that controls the generation of implication constraints i e ON or OFE 7 1 3 ctrl knapcov This f
77. taining the creation number of the node that has been selected for evaluation 52 zlp A double containing the value of the LP solution zprimal A double containing the value of the primal solution rank A double to hold the rank to be associated with the current node The unevaluated nodes of the branch and bound tree are kept in a list The nodes in the list are in order of decreasing rank values When new nodes are generated either by the default division scheme or the division scheme specified by the appl divide function each of them receives a rank value provided either by the default rank function or by the function provided by the appl rank function The rank value of the node is used to insert it at the proper place in the list of unevaluated nodes When a new node has to be selected MINTO will always take the node at the head of the list The default rank function takes the LP value associated with the node as rank which results in a best bound search of the branch and bound tree The following example shows how appl rank can be used to implement the strategy that starts with depth first and switches to best bound as soon as a primal feasible solution has been found E_RANK C include lt stdio h gt include minto h static unsigned switched FALSE appl_rank unsigned appl_rank id depth creation zlp zprimal rank int id identification of active minto long depth node identification
78. that the application has the opportunity to undo the temporary modifications 8 3 bypass integral This function allows an application to bypass the test to determine if the current LP solution is integral PARAMETERS indicator An unsigned integer to hold a status indicator that controls the deactivation of the integrality test i e ON or OFE The function appl primal is intended to provide the application an opportunity to take a fractional LP solution and use it to find an integral solution Consequently when MINTO finds that the current LP so lution is integral it does not call appl primal However there are also situations in which an application may want to take an integral LP solution and use it to find an improved integral solution Note that if the integrality test is bypassed the integrality test should be incorporated in appl primal 58 9 Miscellaneous Functions 9 1 wrt prob This function writes the active formulation i e the formulation currently loaded in the LP solver to a specified file in MPS format PARAMETERS fname A character string specifying the name of the file to which the active formulation should be written The following example shows how wrt prob can be used to write the active formulation to a file E_WRITE C include lt stdio h gt include minto h WriteActive void WriteActive wrt_prob active mps If an error occurs then the return code of the
79. that the information stored in that variable reflects the current formulation The application program can then access the information by inspecting the fields of the variable The rationale behind this approach is that we want to keep memory management fully within MINTO Note that since only nonzero coefficients are stored the memory required to hold the objective function and constraints varies 13 As it is impossible for the application program to keep track of the indices of the active constraints due to constraint generation and constraint management done by MINTO the only fail safe method for accessing constraint related information is to refer to constraints through names rather than indices However in some cases for instance when an application program only wants to inspect constraints of the original formulation which are not affected by constraint generation and constraint management using names would be rather cumbersome To overcome these difficulties the following scheme has been adopted for MINTO All information access for variables and constraints is done through indices For variables the valid indices are in the range 0 up to the number of variables and for constraints the valid indices are in the range O up to the number of constraints However to provide a fail safe access mechanism MINTO has besides the default no names operating mode a names operating mode in which names are associated with each variable and eac
80. the default value of the threshold by its own and that this value is available through the parameter threshold If threshold is set to INE MINTO assumes that the active problem is infeasible and that the node can be fathomed PARAMETERS id An integer containing the identification of the active MINTO copy zlp A double containing the value of the LP solution change A double containing the total change in the value of the LP solution over the last three iterations threshold A double to hold the threshold to be used to detect tailing off When MINTO processes a node it monitors the changes in the value of the LP solutions from iteration to iteration If it detects that the total change in the value of the LP solution in the last three iterations is less than 0 5 percent i e 0 005 times the value of the current LP solution it forces MINTO to branch The following example shows how appl terminatenode can be used to override MINTO s default scheme and continue generating constraints as long as violated constraints are identified E_TERMND C include lt stdio h gt include minto h appl_terminatenode unsigned appl terminatenode id zlp change threshold int id double zlp double change double threshold threshold 0 0 return YES 47 6 17 appl divide This function allows the application to provide a partition of the set of solutions by either specifying bounds for one or more
81. the arrays needed to hold the original formulation with the standard C memory allocation function calloc that the coefficient matrix has to be specified 24 column wise and that even in the case that an application does not want to use names the arrays asso ciated with variable and constraint names are nonempty For every name at least the null character has to be given The following example shows how appl_mps can be used to initialize the original formulation all vari ables are binary all objective coefficients are 1 0 all senses are lt all right hand sides are 1 0 the coefficient matrix is an identity matrix and neither variables nor constraints have names E_MPS C include lt stdio h gt include minto h define SIZE 10 appl mps unsigned appl mps id vent ccnt nzcnt vobj vlb vub vtype csense crhs vfirst vind vcoef vstorsz vstore vname cstorsz cstore cname int id identification of active minto int vcnt number of variables int ccnt number of constraints int nzcnt number of nonzero s double vobj objective coefficients of the variables double vlb lower bounds on the variables double vub upper bounds on the variables char vtype types of the variables i e C B or I char csense senses of the constraints i e L E or G double crhs right hand side
82. the solution of the active formulation PARAMETERS indicator An unsigned integer to hold a status indicator that controls the deactivation of the LP solver i e ON or OFE In branch and price algorithms the initial formulation associated with a node is usually determined only when the node is selected for processing as opposed to when the node is created The reason is that many new variables may have been created between the time the node was created and the time it is selected for processing and that some of these variables have to be deleted fixed at zero Note that bypassing the solution of the active LP does not mean that there is no current LP solution The current LP solution does exist and is equal to the last LP solution except in the case a new node has been selected In the case a new node has been selected the value of the LP solution is equal to the value of the LP solution associated with the parent node and the LP solution consists of zeroes for all variables 8 2 bypass fathom This function allows an application to bypass the test to determine if the processing of the current node can be terminated PARAMETERS indicator An unsigned integer to hold a status indicator that controls the deactivation of the fathom test i e ON or OFE If an application program wants to evaluate the effect of some temporary modifications to the active for mulation on the LP solution the fathoming tests have to be deactivated to make sure
83. tion zlp xlp zprimal xprimal ncnt vcnt vind vtype vvalue nzcnt ccnt cfirst cind ccoef csense crhs cname bdim sdim ldim int id long depth long creation double double double double int ncnt zlp xlp zprimal xprimal int vcnt int vind char vtype double vvalue int nzcnt int ccnt int cfirst int cind double ccoef char csense double crhs double cname int bdim int sdim int ldim 1 register int i register double int index zs double mindiff identification of active minto identification depth identification creation value of the LP solution values of the variables value of the primal solution values of the variables variable for number of nodes array for number of variables array for indices of variables array for type of bounds array for value of bounds variable for number of nonzero coefficients array for number of constraints array for positions of first nonzero coefficients array for indices of nonzero coefficients array for values of nonzero coefficients array for senses array for right hand sides array for names Size of bounds arrays size of small arrays size of large arrays frac diff double 1 for inq form i 0 i lt info form form ven
84. tion itself It has to return either YES in which case MINTO assumes that it has to initialize the original formulation by reading an MPS file and it therefore ignores the parameters or NO in which case MINTO assumes that the application initializes the original formulation itself and that it is available through the parameters vcnt ccnt nzcnt vobj vlb vub vtype csense crhs vfirst vind vcoef vstorsz vstore vname cstorsz cstore and cname PARAMETERS id An integer containing the identification of the active MINTO copy vent An integer to hold the number of variables cent An integer to hold the number of constraints nzent An integer to hold the number of nonzero s vobj A pointer to hold an array of doubles to hold the objective coefficients of the variables vlb A pointer to hold an array of doubles to hold the lower bounds on the variables vub A pointer to hold an array of doubles to hold the upper bounds on the variables vtype A pointer to hold an array of characters to hold the types of the variables i e C B or T csense A pointer to hold an array of characters to hold the senses of the constraints i e L E or e crhs A pointer to hold an array of doubles to hold the right hand sides of the constraints vfirst A pointer to hold an array of integers to hold the starting positions of the columns associated with the variables in the arrays vind and vcoef vind A pointer to hold an arra
85. unc tions use problem specific structures A call to an application function temporarily transfers control to the application program which can either accept control or decline control If control is accepted the application program performs the associated task If control is declined MINTO performs a default ac tion which in many cases will be do nothing The user can also exercise control at the first level by selectively deactivating system functions Figure 1 and 2 give flow charts of the underlying algorithm and the associated application functions To differentiate between actions carried out by the system and those carried out by the application pro gram there are different boxes System actions are in solid line boxes and application program actions are in dashed line boxes A solid line box with a dashed line box enclosed is used whenever an action can be performed by both the system and the application program Finally to indicate that an action has to be performed by either the system or the application program but not both a box with one half in solid lines and the other half in dashed lines is used If an application program does not carry out an action but one is required the system falls back to a default action For instance if an application program does not provide a division scheme for the branching task the system will apply the default branching scheme Formulations The concept of a formulation is fundamental
86. unction activates or deactivates generation of lifted knapsack covers PARAMETERS indicator An unsigned integer to hold a status indicator that controls the generation of lifted knapsack covers i e ON or OFE 55 7 1 4 ctrl flowcov This function activates or deactivates generation of simple and extended generalized flow covers PARAMETERS indicator An unsigned integer to hold a status indicator that controls the generation of simple and extended generalized flow covers i e ON or OFE 7 1 5 ctrl output This function sets the output level PARAMETERS indicator An unsigned integer to hold the level of output to be set i e 0 1 or 2 7 2 Linear Programming Control Functions Methods to control the linear programming software directly through MINTO are deprecated In stead the user is urged to see Section 11 for how to gain direct access to the active linear program ming solver and use the interfaces that the LP solver provides MINTO can provide limited control over the run time behavior of the LP solver through a set of control functions Each of these control functions can be called any time during the solution process and changes the parameters of the LP solver For a precise definition of the meaning of the parameters the user is referred to the manual of the LP solver 7 3 ctrl Ipmethod This function selects the type of algorithm that is used to solve the active formulation PARAMETERS selector An integer sp
87. variables or generating one or more constraints or both It has to return either FAILURE in which case MINTO assumes that the application wants to use the default division scheme and it therefore ignores the parameters or SUCCESS in which case MINTO assumes that the application constructed a partition which is available through the parameters or INSUFFICIENT signaling that more memory i e larger arrays is required to store the partition in which case MINTO increases the available memory and calls the function again PARAMETERS id An integer containing the identification of the active MINTO copy depth A long containing the depth in the tree of the node that has been selected for evaluation creation A long containing the creation number of the node that has been selected for evaluation zlp A double containing the value of the LP solution xlp An array of doubles containing the values of the variables zprimal A double containing the value of the primal solution xprimal An array of doubles containing the values of the variables associated with the primal solu tion nent An integer to hold the number of nodes in the division vent An array of integers to hold the number of variables for which a bound is specified for each node vind An array of integers to hold the indices of the variables for which a bound is specified vtype An array of characters to hold the types of bounds i e lower bound T or upper bound U
88. y of integers to hold the indices of the nonzero coefficients vcoef A pointer to hold an array of doubles to hold the nonzero coefficients vstorsz A pointer to hold an integer to hold the total number of characters including the null characters in the names of the variables vstore A pointer to hold an array of characters to hold the names of the variables vname A pointer to hold an array of character pointers to hold the starting positions of the names of the variables in the array vstore cstorsz An integer to hold the total number of characters including the null characters in the names of the constraints cstore A pointer to hold an array of characters to hold the names of the constraints cname A pointer to hold an array of character pointers to hold the starting positions of the names of the constraints in the array cstore By default MINTO assumes that it has to initialize the original formulation by reading an MPS file avail able in the current working directory However for some applications it is much more convenient to generate the original formulation directly within MINTO However MINTO still requires a problem name to be specified on the command line This name will serve as both problem name and filename MINTO always opens a logfile filename log to write out information that may be useful to determine the cause of a premature exit in case this occurs Note that the application has to allocate memory for all

Download Pdf Manuals

Related Search

Related Contents

Silicon Anomaly List for SHARC ADSP-21061  スライディングチューブ ST-C6 スライディングチューブ ST  Panasonic SC-HC35 docking speaker  ASUS Z97-P T9385 User's Manual  1 - Goodman  Bedienungsanleitung - CGS Prozessanalytik  

Copyright © All rights reserved. Failed to retrieve file