MilpSolve

From TomWiki
Revision as of 10:58, 12 August 2014 by Bjorn (talk | contribs) (→‎MIP structure, substructure of Prob)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

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.