MilpSolve
Purpose
Solve mixed integer linear programming problems (MILP).
MILPSOLVE solves problems of the form
where , and . The variables , the index subset of are restricted to
be integers.
Calling Syntax
Result = tomRun('MILPSOLVE',Prob, 1); or
Prob = ProbCheck(Prob, 'MILPSOLVE');
Result = milpsolveTL(Prob);
PrintResult(Result,1);
Inputs
Prob structure
The following fields are used in Prob: | |
---|---|
FieldName | Value |
x_L, x_U | Lower and upper bounds on variables. (Must be dense). |
b_L, b_U | Lower and upper bounds on linear constraints. (Must be dense). |
A | Linear constraint matrix. (Sparse or dense). |
QP.c | Linear objective function coefficients, size nx1. |
BIG | Definition of infinity. Default is 1e30. |
LargeScale | Defines if milpsolveTL will convert the A matrix to a sparse matrix or not.
Largescale ! = 0 - sparse LargeScale = 0 - dense Default is to use the A matrix just as it is defined. |
PriLevOpt | Specifies the printlevel that will be used by MILPSOLVE.
0 (NONE) No outputs 1 (NEUTRAL) Only some specific debug messages in debug print rou- tines are reported. 2 (CRITICAL) Only critical messages are reported. Hard errors like instability, out of memory. 3 (SEVERE) Only severe messages are reported. Errors. 4 (IMPORTANT) Only important messages are reported. Warnings and Errors. 5 (NORMAL) Normal messages are reported. 6 (DETAILED) Detailed messages are reported. Like model size, con- tinuing B&B improvements. 7 (FULL) All messages are reported. Useful for debugging purposes and small models. Default print level is 0, no outputs. PriLevOpt < 0 is interpreted as 0, and larger than 7 is interpreted as 7. |
MaxCPU | Maximal CPU Time (in seconds) to be used by MILPSOLVE, stops with best point found. |
MILPSOLVE | Substructure defininig milpSolve specific options, see the table below. |
MIP | Substructure with parameters specific to mixed integer programming problems in TOMLAB, see the table below. |
MILPSOLVE structure, substructure of Prob
Solver specific options structure.
MILPSOLVE | The following fields are used in Prob.MILPSOLVE: | |
---|---|---|
Field | Value | |
ANTI_DEGEN | Binary vector. If empty, no anti-degeneracy handling is applied. If the length (i) of the vector is less than 8 elements,only the i first modes are considered. Also if i is longer than 8 elements, the elements after element8 are ignored.
ANTI_DEGEN specifies if special handling must be done to reduce de- generacy/cycling while solving. Setting this flag can avoid cycling, but can also increase numerical instability. ANTIDEGEN FIXEDVARS ! = 0 Check if there are equality slacks in the basis and try to drive them out in order to reduce chance of degeneracy in Phase 1. ANTIDEGEN COLUMNCHECK != 0 ANTIDEGEN STALLING != 0 ANTIDEGEN NUMFAILURE != 0 ANTIDEGEN LOSTFEAS != 0 ANTIDEGEN INFEASIBLE != 0 ANTIDEGEN DYNAMIC != 0 ANTIDEGEN DURINGBB != 0 | |
basis | If empty or erroneous, default basis is used. Default start base is the all slack basis (the default simplex starting basis).
Prob.MILPSOLVE.basis stores the basic variables. If an element is less then zero then it means on lower bound, else on upper bound. Element 0 of the array is unused. The default initial basis is bascolumn[x] = -x. By MILPSOLVE convention, a basic variable is always on its lower bound, meaning that basic variables is always represented with a minus sign. When a restart is done, the basis vector must be assigned a correct starting basis. | |
BASIS_CRASH | The set_basiscrash function specifies which basis crash mode MILP- SOLVE will used.
When no base crash is done (the default), the initial basis from which MILPSOLVE starts to solve the model is the basis containing all slack or artificial variables that is automatically associates with each constraint. When base crash is enabled, a heuristic "crash procedure" is executed before the first simplex iteration to quickly choose a basis matrix that has fewer artificial variables. This procedure tends to reduce the num- ber of iterations to optimality since a number of iterations are skipped. MILPSOLVE starts iterating from this basis until optimality. BASIS_CRASH ! = 2 - No basis crash BASIS_CRASH = 2 - Most feasible basis Default is no basis crash. | |
BB_DEPTH_LIMIT | Sets the maximum branch-and-bound depth. This value makes sense only if there are integer, semi-continuous or SOS variables in the model so that the branch-and-bound algorithm is used to solve the model. The branch-and-bound algorithm will not go deeper than this level. When BB DEPTH LIMIT i set to 0 then there is no limit to the depth. The default value is -50. A positive value means that the depth is absolute. A negative value means a relative B&B depth. The "order" of a MIP problem is defined to be 2 times the number of binary variables plus the number of SC and SOS variables. A relative value of -x results in a maximum depth of x times the order of the MIP problem. | |
BB_FLOOR_FIRST | Specifies which branch to take first in branch-and-bound algorithm. Default value is 1.
BB_FLOOR_FIRST = 0 (BRANCH CEILING) Take ceiling branch first BB_FLOOR_FIRST = 1 (BRANCH FLOOR) Take floor branch first BB_FLOOR_FIRST = 2 (BRANCH AUTOMATIC) MILPSOLVE decides which branch being taken first | |
BB_RULE | Specifies the branch-and-bound rule. Default value is 0.
BB_RULE = 0 (NODE_FIRSTSELECT) Select lowest indexed non- integer column BB_RULE = 1 (NODE_GAPSELECT) Selection based on distance from the current bounds BB_RULE = 2 (NODE_RANGESELECT) Selection based on the largest current bound BB_RULE = 3 (NODE_FRACTIONSELECT) Selection based on largest fractional value BB_RULE = 4 (NODE_PSEUDOCOSTSELECT4) Simple, unweighted pseudo-cost of a variable BB_RULE = 5 (NODE_PSEUDONONINTSELECT) This is an ex- tended pseudo-costing strategy based on minimizing the number of in- teger infeasibilities. BB RULE = 6 (NODE_PSEUDORATIOSELECT) This is an extended pseudo-costing strategy based on maximizing the normal pseudo-cost divided by the number of infeasibilities. Effectively, it is similar to (the reciprocal of ) a cost/benefit ratio. BB_RULE = 7 (NODE_USERSELECT) | |
BB_RULE_ADD | Additional values for the BB RULE. BB RULE is a vector. If the length i of the vector is less than 10 elements, only the i first modes are considered. Also if i is longer than 10 elements, the elements after element 10 is ignored.
BB_RULE ADD(1) ! = 0 (NODE_WEIGHTREVERSEMODE) BB_RULE ADD(2) ! = 0 (NODE BRANCHREVERSEMODE) In case when get bb floorfirst is BRANCH AUTOMATIC, select the opposite direction (lower/upper branch) that BRANCH AUTOMATIC had cho- sen. BB_RULE_ADD(3) ! = 0 (NODE_GREEDYMODE) BB_RULE_ADD(4) ! = 0 (NODE_PSEUDOCOSTMODE) BB_RULE_ADD(5) ! = 0 (NODE_DEPTHFIRSTMODE) Select the node that has already been selected before the number of times BB_RULE_ADD(6) ! = 0 (NODE_RANDOMIZEMODE) BB_RULE_ADD(7) ! = 0 (NODE_DYNAMICMODE) When NODE DEPTHFIRSTMODE is selected, switch off this mode when a first solution is found. BB_RULE_ADD(8) ! = 0 (NODE_RESTARTMODE) BB_RULE_ADD(9) ! = 0 (NODE_BREADTHFIRSTMODE) Select the node that has been selected before the fewest number of times or not at all BB RULE ADD(10) ! = 0 (NODE_AUTOORDER) | |
BFP | Defines which Basis Factorization Package that will be used by MILP- SOLVE.
BFP = 0 : LUSOL BFP = 1 : built in etaPHI from MILPSOLVE v3.2 BFP = 2 : Additional etaPHI BFP = 3 : GLPK Default BFP is LUSOL. | |
BREAK_AT_FIRST | Specifies if the branch-and-bound algorithm stops at the first found so- lution (BREAK_AT_FIRST != 0) or not (BREAK_AT_FIRST = 0). De- fault is not to stop at the first found solution. | |
BREAK_AT_VALUE | Specifies if the branch-and-bound algorithm stops when the object value is better than a given value. The default value is (-) infinity. | |
EPAGAP | Specifies the absolute MIP gap tolerance for the branch and bound algo- rithm. This tolerance is the difference between the best-found solution yet and the current solution. If the difference is smaller than this toler- ance then the solution (and all the sub-solutions) is rejected. The default value is 1e-9. | |
EPGAP | Specifies the relative MIP gap tolerance for the branch and bound algo- rithm. The default value is 1e-9. | |
EPSB | Specifies the value that is used as a tolerance for the Right Hand Side (RHS) to determine whether a value should be considered as 0. The default epsb value is 1.0e-10 | |
EPSD | Specifies the value that is used as a tolerance for reduced costs to deter- mine whether a value should be considered as 0. The default epsd value is 1e-9. If EPSD is empty, EPSD is read from Prob.optParam.eps f. | |
EPSEL | Specifies the value that is used as a tolerance for rounding values to zero. The default epsel value is 1e-12. | |
EPSINT | Specifies the tolerance that is used to determine whether a floating- point number is in fact an integer. The default value for epsint is 1e-7. Changing this tolerance value can result in faster solving times, but the solution is less integer. | |
EPSPERTURB | Specifies the value that is used as perturbation scalar for degenerative problems. The default epsperturb value is 1e-5. | |
EPSPIVOT | Specifies the value that is used as a tolerance pivot element to determine whether a value should be considered as 0. The default epspivot value is 2e-7 | |
IMPROVEMENT_LEVEL | Specifies the iterative improvement level.
IMPROVEMENT LEVEL = 0 (IMPROVE NONE) improve none IMPROVEMENT LEVEL = 1 (IMPROVE FTRAN) improve FTRAN IMPROVEMENT LEVEL = 2 (IMPROVE BTRAN) improve BTRAN IMPROVEMENT LEVEL = 3 (IMPROVE SOLVE) improve FTRAN + BTRAN. IMPROVEMENT LEVEL = 4 (IMPROVE INVERSE) triggers automatic inverse accuracy control in the dual simplex, and when an error gap is exceeded the basis is reinverted Choice 1,2,3 should not be used with MILPSOLVE 5.1.1.3, because of problems with the solver. Default is 0. | |
LoadFile | File that contains the model. If LoadFile is a nonempty string which corresponds to actual file, then the model is read from this file rather than from the Prob struct. | |
LoadMode | 1 - LP - MILPSOLVE LP format
2 - MPS - MPS format 3 - FMPS - Free MPS format A default value for this field does not exist. Both LoadFile and Load- Mode must be set if a problem will be loaded. If there is something wrong with LoadMode or LoadFile, an error mes- sage will be printed and MILPSOLVE will be terminated. Leave Load- Mode and LoadFile empty if the problem not will be loaded from file. | |
LogFile | Name of file to print MILPSOLVE log on. | |
MAXIMIZE | If MAXIMIZE ! = 0, MILPSOLVE is set to maximize the objective function, default is to minimize. | |
MAX_PIVOT | Sets the maximum number of pivots between a re-inversion of the matrix. Default is 42. | |
NEG_RANGE | Specifies the negative value below which variables are split into a negative and a positive part. This value must always be zero or negative. If a positive value is specified, then 0 is taken. The default value is -1e6. | |
PRESOLVE | Vector containing possible presolve options. If the length i of the vector is less than 7 elements, only the i first modes are considered. Also if i is longer than 7 elements, the elements after element 7 is ignored.
PRESOLVE(1) ! = 0 (PRESOLVE ROWS) Presolve rows PRESOLVE(2) ! = 0 (PRESOLVE COLS) Presolve columns PRESOLVE(3) ! = 0 (PRESOLVE LINDEP) Eliminate linearly depen- dent rows PRESOLVE(4) ! = 0 (PRESOLVE SOS) Convert constraints to SOSes (only SOS1 handled) PRESOLVE(5) ! = 0 (PRESOLVE REDUCEMIP) If the phase 1 solu- tion process finds that a constraint is redundant then this constraint is deleted. PRESOLVE(6) ! = 0 (PRESOLVE DUALS) Calculate duals PRESOLVE(7) ! = 0 (PRESOLVE SENSDUALS) Calculate sensitivity if there are integer variables Default is not to do any presolve. | |
PRICING_RULE | The pricing rule can be one of the following rules.
PRICING_RULE = 0 Select first (PRICER_FIRSTINDEX) PRICING_RULE = 1 Select according to Dantzig (PRICER_DANTZIG) PRICING_RULE = 2 Devex pricing from Paula Harris (PRICER_DEVEX) PRICING_RULE = 3 Steepest Edge (PRICER STEEPESTEDGE) | |
PRICING_MODE | Additional pricing settings, any combination of the modes below. This is a binary vector. If the length i of the vector is less than 7 elements, only the i first modes are considered. Also if i is longer than 7 elements, the elements after element 7 is ignored.
PRICE_PRIMALFALLBACK ! = 0 In case of Steepest Edge, fall back to DEVEX in primal. PRICE_MULTIPLE ! = 0 Preliminary implementation of the multiple pricing scheme. This means that attractive candidate entering columns from one iteration may be used in the subsequent iteration, avoiding full updating of reduced costs. In the current implementation, MILPSOLVE only reuses the 2nd best entering column alternative. PRICE_PARTIAL ! = 0 Enable partial pricing PRICE_ADAPTIVE ! = 0 Temporarily use First Index if cycling is detected PRICE_RANDOMIZE ! = 0 Adds a small randomization effect to the selected pricer PRICE_LOOPLEFT ! = 0 Scan entering/leaving columns left rather than right PRICE_LOOPALTERNATE ! = 0 Scan entering/leaving columns alternatingly left/right Default basis is PRICER DEVEX combined with PRICE ADAPTIVE. | |
sa | Struct containing information of the sensitivity analysis (SA) MILPSOLVE will perform.
sa.obj =! 0 Perform sensitivity analysis on the objective function sa.obj = 0 Do not perform sensitivity analysis on the objective function sa.rhs =! 0 Perform sensitivity analysis on the right hand sides. sa.rhs = 0 Do not perform sensitivity analysis on the right hand sides. | |
SaveFileAfter | Name of a file to save the MILPSOLVE object after presolve.The name must be of type string (char), Example: Prob.MILPSOLVE.SaveFileAfter = 'save2' If the type is not char SaveFileBefore is set to save2.[file extension]. | |
SaveFileBefore | Name of a file to save the MILPSOLVE object before presolve. The name must be of type string (char), Example: Prob.MILPSOLVE.SaveFileBefore = 'save1'. If the type is not char SaveFileBefore is set to save1.[file extension]. | |
SaveMode | 1 - LP - MILPSOLVE LP format
2 - MPS - MPS format 3 - FMPS - Free MPS format If empty, the default format LP is used. | |
SCALE_LIMIT | Sets the relative scaling convergence criterion to the absolute value of SCALE_LIMIT for the active scaling mode. The integer part of SCALE_LIMIT specifies the maximum number of iterations. Default is 5. | |
SCALING_ALG | Specifies which scaling algorithm will be used by MILPSOLVE.
0 No scaling algorithm 1 (SCALE EXTREME) Scale to convergence using largest absolute value 2 (SCALE RANGE) Scale based on the simple numerical range 3 (SCALE MEAN) Numerical range-based scaling 4 (SCALE GEOMETRIC) Geometric scaling 7 (SCALE CURTISREID) Curtis-reid scaling Default is 0, no scaling algorithm. | |
SCALING_ADD | Vector containing possible additional scaling parameters. If the length (i) of the vector is less than 7 elements, only the i first modes are considered. Also if i is longer than 7 elements, the elements after element 7 is ignored. SCALING ADD ! = 0 (SCALE_QUADRATIC)
SCALING ADD ! = 0 (SCALE_LOGARITHMIC) Scale to convergence using logarithmic mean of all values SCALING_ADD ! = 0 (SCALE_USERWEIGHT) User can specify scalars SCALING_ADD ! = 0 (SCALE_POWER2) also do Power scaling SCALING_ADD ! = 0 (SCALE_EQUILIBRATE) Make sure that no scaled number is above 1 SCALING_ADD ! = 0 (SCALE_INTEGERS) Also scaling integer vari- ables SCALING_ADD ! = 0 (SCALE_DYNUPDATE) Dynamic update Default is 0, no additional mode. Settings SCALE_DYNUPDATE is a way to make sure that scaling factors are recomputed. In that case, the scaling factors are recomputed also when a restart is done. | |
SIMPLEX_TYPE | Sets the desired combination of primal and dual simplex algorithms.
5 (SIMPLEX_PRIMAL_PRIMAL) Phase1 Primal, Phase2 Primal 6 (SIMPLEX_DUAL_PRIMAL) Phase1 Dual, Phase2 Primal 9 (SIMPLEX_PRIMAL_DUAL) Phase1 Primal, Phase2 Dual 10 (SIMPLEX_DUAL_DUAL) Phase1 Dual, Phase2 Dual Default is SIMPLEX DUAL PRIMAL (6). | |
SOLUTION_LIMIT | Sets the solution number that will be returned. This value is only consid- ered if there are integer, semi-continuous or SOS variables in the model so that the branch-and-bound algorithm is used. If there are more solutions with the same objective value, then this number specifies which solution must be returned. Default is 1. | |
sos | List of structs containing data about Special Ordered Sets (SOS). See below for further description. |
MIP structure, substructure of Prob
Options specific to mixed integer programming problems.
The following fields are used in Prob.MIP: | |
---|---|
FieldName | Value |
IntVars | Defines which variables are integers, of general type I or binary type B Variable indices should be in the range [1,...,n].
IntVars is a logical vector ==> x(find(IntVars > 0)) are integers IntVars is a vector of indices ==> x(IntVars) are integers (if [], then no integers of type I or B are defined) variables with x L=0 and x U=1, is are set to binary. It is possible to combine integer and semi-continuous type to obtain the semi-integer type. |
fIP | This parameter specifies the initial "at least better than" guess for objective function. This is only used in the branch-and-bound algorithm when integer variables exist in the model. All solutions with a worse objective value than this value are immediately rejected. The default is infinity. |
SC | A vector with indices for variables of type semi-continuous (SC), a logical vector or a scalar (see MIP.IntVars). A semi-continuous variable i takes either the value 0 or some value in the range [x L(i), x U(i)]. It is possible to combine integer and semi-continuous type to obtain the semi-integer type. |
sos1 | List of structures defining the Special Ordered Sets of Order One (SOS1). For SOS1 set k, sos1(k).var is a vector of indices for variables of type SOS1 in set k, sos1(k).row is the priority of SOS k in the set of SOS1 and sos1(k).weight is a vector of the same length as sos1(k).var and it describes the order MILPSOLVE will weight the variables in SOS1 set k.
a low number of a row and a weight means high priority. |
sos2 | List of n structures defining the Special Ordered Sets (SOS) of Order Two (SOS2). (see MIP.sos1) |
Outputs
Result | Structure with result from optimization. The following fields are changed: | |
---|---|---|
x_k | Optimal solution (or some other solution if optimum could not been found) | |
f_k | Optimal objective value. | |
v_k | [rc; duals]. If Reduced cost and dual variables are not available, then v_k is empty. | |
ExitFlag | TOMLAB information parameter.
0 = Optimal solution found. 1 = Suboptimal solution or user abort. 2 = Unbounded solution. 3 = Numerical failure. 4 = Infeasible model. 10 = Out of memory. 11 = Branch and bound stopped. | |
ExitText | Status text from MILPSOLVE. | |
Inform | MILPSOLVE information parameter.
-2 = Out of memory. 0 = Optimal solution found. 1 = Suboptimal solution. 2 = Infeasible model. 3 = Unbounded solution. 4 = Degenerate solution. 5 = Numerical failure. 6 = User abort. 7 = Timeout. 10 = Branch and bound failed. 11 = Branch and bound stopped. 12 = Feasible branch and bound solution. 13 = No feasible branch and bound solution. Other = Unknown status. | |
Iter | The total number of nodes processed in the branch-and-bound algorithm. Is only applicable if the model contains integer variables. In the case of an LP model Result.Iter contains the number of iterations. This is however not documented. | |
MinorIter | The total number of Branch-and-bound iterations. When the problem is LP, MinorIter equals Result.Iter | |
MILPSOLVE.basis | Optimal basis, on the format described above under Prob.MILPSOLVE.basis. | |
MILPSOLVE.MaxLevel | The deepest Branch-and-bound level of the last solution. Is only applicable if the model contains integer variables. | |
MILPSOLVE.sa.objStatus | 1 successful
0 SA not requested -1 Error: error from MILPSOLVE -3 no SA available | |
MILPSOLVE.sa.ObjLower | An array that will contain the values of the lower limits on the objective function. | |
MILPSOLVE.sa.ObjUpper | An array that will contain the values of the upper limits on the objective function. | |
MILPSOLVE.sa.RhsStatus | see MILPSOLVE.sa.objStatus. | |
MILPSOLVE.sa.RhsLower | An array that will contain the values of the lower limits on the RHS. | |
MILPSOLVE.sa.RhsUpper | An array that will contain the values of the upper limits on the RHS. | |
xState | State of each variable
0 - free variable, 1 - variable on lower bound, 2 - variable on upper bound, 3 - variable is fixed, lower bound = upper bound. | |
bState | State of each linear constraint
0 - Inactive constraint, 1 - Linear constraint on lower bound, 2 - Linear constraint on upper bound, 3 - Linear equality constraint. |