MipSolve: Difference between revisions
m (→Outputs) |
m (→Outputs) |
||
(8 intermediate revisions by the same user not shown) | |||
Line 88: | Line 88: | ||
|||''MaxCPU''||Maximal CPU Time (in seconds) to be used by mipSolve, stops with best point found. | |||''MaxCPU''||Maximal CPU Time (in seconds) to be used by mipSolve, stops with best point found. | ||
|-valign="top" | |-valign="top" | ||
|||''PriLevOpt''||Print level in | |||''PriLevOpt''||Print level in sub-solver, see the documentation for the solver. | ||
|- | |-valign="top" | ||
|||''PriLev''||Print level in ''mipSolve'' (default 1). Also see optParam.IterPrint. | |||''PriLev''||Print level in ''mipSolve'' (default 1). Also see optParam.IterPrint. | ||
|-valign="top" | |-valign="top" | ||
|||''WarmStart''||If true, >0, mipSolve reads the output from the last run from Prob.mipSolve, if it exists. If it doesn't exist, mipSolve attempts to open and read warm start data from mat-file mipSolveSave.mat. | |||''WarmStart''||If true, >0, mipSolve reads the output from the last run from Prob.mipSolve, if it exists. If it doesn't exist, mipSolve attempts to open and read warm start data from mat-file mipSolveSave.mat. <br>mipSolve uses the warm start information to continue from the last run. The mat-file mipSolveSave.mat is saved every Prob.MIP.SaveFreq iteration | ||
|-valign="top" | |||
mipSolve uses the warm start information to continue from the last run. The mat-file mipSolveSave.mat is saved every Prob.MIP.SaveFreq iteration | |||''QP.B''||Active set ''B_0 ''at start: <br>''B''(''i'') = 1: Include variable ''x''(''i'') is in basic set. <br>''B''(''i'') = 0: Variable ''x''(''i'') is set on its lower bound. <br>''B''(''i'') = ''-''1: Variable ''x''(''i'') is set on its upper bound. | ||
|- | |||
|||''QP.B''||Active set ''B_0 ''at start: | |||
''B''(''i'') = 1: Include variable ''x''(''i'') is in basic set. | |||
''B''(''i'') = 0: Variable ''x''(''i'') is set on its lower bound. | |||
''B''(''i'') = ''-''1: Variable ''x''(''i'') is set on its upper bound. | |||
|-valign="top" | |-valign="top" | ||
|||''SolverLP''||Name of the solver used for the initial LP subproblem. If empty, the best available solver with a license is picked from a list. | |||''SolverLP''||Name of the solver used for the initial LP subproblem. If empty, the best available solver with a license is picked from a list. <br>Note - If using MINOS, use the special LP interface LP-MINOS | ||
Note - If using MINOS, use the special LP interface LP-MINOS | |||
|-valign="top" | |-valign="top" | ||
|||''SolverDLP''||Name of the solver used for dual LP subproblems. If empty, SolverLP is used. | |||''SolverDLP''||Name of the solver used for dual LP subproblems. <br>If empty, SolverLP is used. <br>If SolverLP/SolverDLP is a SOL solver (SNOPT, MINOS or NPSOL), the SOL.optPar and SOL.PrintFile is used: See help minosTL.m, npsolTL.m or snoptTL.m for how to set these parameters. | ||
If SolverLP/SolverDLP is a SOL solver (SNOPT, MINOS or NPSOL), the SOL.optPar and SOL.PrintFile is used: See help minosTL.m, npsolTL.m or snoptTL.m for how to set these parameters. | |||
|-valign="top" | |-valign="top" | ||
|||''MIP''||Structure in ''Prob'', ''Prob.MIP''. Defines integer optimization parameters: | |||''MIP''||Structure in ''Prob'', ''Prob.MIP''. Defines integer optimization parameters: | ||
|-valign="top" | |-valign="top" | ||
|||''MIP.IntVars''||If empty, all variables are assumed non-integer. | |||''MIP.IntVars''||If empty, all variables are assumed non-integer. <br>If islogical(IntVars) (i.e. all elements are 0/1), then 1 = integer variable, 0 = continuous variable. <br>If any element >1, IntVars is the indices for integer variables | ||
If islogical(IntVars) (i.e. all elements are 0/1), then 1 = integer variable, 0 = continuous variable. | |||
If any element >1, IntVars is the indices for integer variables | |||
|-valign="top" | |-valign="top" | ||
|||''MIP.VarWeight''||Weight for each variable in the variable selection phase. A lower value gives higher priority. Setting Prob.MIP.VarWeight = c; for knapsack problems improve convergence. | |||''MIP.VarWeight''||Weight for each variable in the variable selection phase. A lower value gives higher priority. Setting Prob.MIP.VarWeight = c; for knapsack problems improve convergence. | ||
|- | |-valign="top" | ||
|||''MIP.DualGap''||mipSolve stops if the duality gap is less than DualGap | |||''MIP.DualGap''||mipSolve stops if the duality gap is less than DualGap. <br>E.g. DualGap = 1, implies a stop at the first integer solution. <br>E.g. DualGap = 0.01, stop if the solution less than one percent from the optimal solution. | ||
|-valign="top" | |||
E.g. DualGap = 1, implies a stop at the first integer solution. | |||
E.g. DualGap = 0.01, stop if the solution less than one percent from the optimal solution. | |||
|- | |||
|||''MIP.fIP''||An upper bound on the IP value wanted. Makes it possible to cut branches and avoid node computations. Used even if xIP not given. | |||''MIP.fIP''||An upper bound on the IP value wanted. Makes it possible to cut branches and avoid node computations. Used even if xIP not given. | ||
|- | |-valign="top" | ||
|||''MIP.xIP''||The ''x''-value giving the ''fIP ''value, if a solution (xIP, fIP) is known. | |||''MIP.xIP''||The ''x''-value giving the ''fIP ''value, if a solution (xIP, fIP) is known. | ||
|-valign="top" | |-valign="top" | ||
|||''MIP.NodeSel''||Node selection method: | |||''MIP.NodeSel''||Node selection method: <br>0: Depth first. Priority on nodes with more integer components. <br>1: Breadth first. Priority on nodes with more integer components. <br>2: Depth first. When integer solution found, use NodeSel = 1 (Default). <br>3: Pure LIFO (Last in, first out) Depth First <br>4: Pure FIFO (First in, first out) Breadth First <br>5: Pure LIFO Depth First. When integer solution found, use NodeSel = 4. | ||
|-valign="top" | |||
0: Depth first. Priority on nodes with more integer components. | |||''MIP.VarSel''||Variable selection method in branch and bound.<br> 1: Use variable with most fractional value <br>2: Use gradient and distance to nearest integer value | ||
|-valign="top" | |||
1: Breadth first. Priority on nodes with more integer components. | |||
2: Depth first. When integer solution found, use NodeSel = 1 (Default). | |||
3: Pure LIFO (Last in, first out) Depth First | |||
4: Pure FIFO (First in, first out) Breadth First | |||
5: Pure LIFO Depth First. When integer solution found, use NodeSel = 4. | |||
|- | |||
|||''MIP.VarSel''||Variable selection method in branch and bound. | |||
|- | |||
|||''MIP.KNAPSACK''||If solving a knapsack problem, set to true (1) to use a knapsack heuristic. | |||''MIP.KNAPSACK''||If solving a knapsack problem, set to true (1) to use a knapsack heuristic. | ||
|- | |- | ||
|||''MIP.ROUNDH''||If = 1, use a rounding heuristic. Default 1. | |||''MIP.ROUNDH''||If = 1, use a rounding heuristic. Default 1. | ||
|- | |-valign="top" | ||
|||''MIP.SaveFreq''||Warm start info saved on mipSolveSave.mat every SaveFreq iteration. (default -1, i.e. no warm start info is saved) | |||''MIP.SaveFreq''||Warm start info saved on mipSolveSave.mat every SaveFreq iteration. (default -1, i.e. no warm start info is saved) | ||
|- | |- | ||
|||''Solver''||Options for the LP subproblem: | |||''Solver''||Options for the LP subproblem: | ||
|-valign="top" | |-valign="top" | ||
|||''Solver.method''||Rule to select new variables in DualSolve/lpSimplex: | |||''Solver.method''||Rule to select new variables in DualSolve/lpSimplex:<br>0: Minimum reduced cost, sort variables increasing (default). <br> 1: Bland's Anti-Cycling Rule <br>2: Minimum reduced cost. Dantzig's rule. | ||
|-valign="top" | |||
0: Minimum reduced cost, sort variables increasing (default). | |||''optParam''||Structure in Prob. <br>Fields used in Prob.optParam, also in sub-solvers: | ||
1: Bland's Anti-Cycling Rule | |||
2: Minimum reduced cost. Dantzig's rule. | |||
|- | |||
|||''optParam''||Structure in Prob. Fields used in Prob.optParam, also in sub solvers: | |||
|- | |- | ||
|||''optParam.MaxIter|| Maximal number of iterations. max(10*dim(x),100) is default. | |||''optParam.MaxIter|| Maximal number of iterations. max(10*dim(x),100) is default. | ||
|- | |-valign="top" | ||
|||''optParam.IterPrint||Print short information each iteration (PriLev > 0 ==> IterPrint = 1) | |||''optParam.IterPrint||Print short information each iteration (PriLev > 0 ==> IterPrint = 1). <br>One line each iteration with:<br> | ||
Iteration number <br>Depth in tree (symbol L[] - empty list, <br>symbol Gap - Dual Gap convergence; <br>date/time stamp, <br>fLP (Optimal f(x) current node), <br>fIPMin (Best integer feasible f(x) found) <br>LowBnd (Lower bound on optimal integer feasible f(x)), <br>Dual Gap in absolut value and percent. <br>The length of the node list L, |L| <br>The Inform and ExitFlag the solver returned at the current node | |||
One line each iteration with: | |-valign="top" | ||
Iteration number | |||
Depth in tree (symbol L[] - empty list, | |||
symbol Gap - Dual Gap convergence; | |||
date/time stamp, | |||
fLP (Optimal f(x) current node), fIPMin (Best integer feasible f(x) found) | |||
LowBnd (Lower bound on optimal integer feasible f(x)), | |||
Dual Gap in absolut value and percent. | |||
The length of the node list L, |L| | |||
The Inform and ExitFlag the solver returned at the current node | |||
|- | |||
|||''optParam.bTol||Linear constraint violation convergence tolerance | |||''optParam.bTol||Linear constraint violation convergence tolerance | ||
|- | |- | ||
|||'' ''||Fields in Prob.optParam that are used | |||'' ''||''Fields in Prob.optParam that are used by lpSimplex and DualSolve (assuming they are set as sub-solvers)'': | ||
|- | |-valign="top" | ||
|||''optParam.eps_f''||Tolerance used for function value tests | |||''optParam.eps_f''||Tolerance used for function value tests | ||
|- | |- | ||
Line 210: | Line 150: | ||
|-valign="top" | |-valign="top" | ||
|||''Iter''||Number of iterations. | |||''Iter''||Number of iterations. | ||
|-valign="top" | |||
|||''ExitFlag''||ExitFlag.<br>0: Global optimal solution found, or integer solution with duality gap less than user tolerance.<br>1: Maximal number of iterations reached.<br>2: Empty feasible set, no integer solution found.<br>3: Rank problems (not used).<br>4: No feasible point found running LP relaxation.<br>5: Illegal ''x_0'' found in LP relaxation.<br>99: Maximal CPU Time used (cputime > Prob.MaxCPU). | |||
|-valign="top" | |||
|||''ExitText''||Text string giving ''ExitFlag'' and ''Inform'' information. | |||
|-valign="top" | |||
|||''Inform''||If ''ExitFlag'' > 0, ''Inform'' = ''ExitFlag'', except if duality gap less than given tolerance (''Inform'' = 6) | |||
|-valign="top" | |||
|||''DualGap''||Relative duality gap, max(0, fIPMin-fLB)/<nowiki>|fIPMin|</nowiki>, if fIPMin ~=0; max(0,fIPMin-fLB) if fIPMin == 0. <br>If fIPMin ~=0: Scale with 100, 100*''DualGap'', to get the percentage duality gap. For absolute value duality gap: scale with fIPMin, fIPMin * ''DualGap'' | |||
|- | |- | ||
|||'' | |||''x_k''||Solution. | ||
|-valign="top" | |||
|- | |||
|||''v_k''||Lagrange parameters (n+m) vector, [Bounds(n); Linear constraints (m)]. | |||''v_k''||Lagrange parameters (n+m) vector, [Bounds(n); Linear constraints (m)]. | ||
|- | |-valign="top" | ||
|||''QP.B''||B Optimal set. B(i)==0 implies inclusion of variable x(i) in basic set. sum(B==1)==length(b) holds. See ''QP.B'' as input. | |||''QP.B''||B Optimal set. B(i)==0 implies inclusion of variable x(i) in basic set. sum(B==1)==length(b) holds. See ''QP.B'' as input. | ||
|- | |-valign="top" | ||
|||''QP.y''||Dual parameters ''y ''(also part of ''Result.v_k''). | |||''QP.y''||Dual parameters ''y ''(also part of ''Result.v_k''). | ||
|- | |-valign="top" | ||
|||''f_k''||Function value | |||''f_k''||Function value c<sup>T</sup>x_k, fIPMin (Best integer feasible solution). | ||
|- | |- | ||
|||''g_k''||Gradient value at optimum, ''c''. | |||''g_k''||Gradient value at optimum, ''c''. | ||
|- | |- | ||
|||''Solver''||Solver used ( | |||''Solver''||Solver used (mipSolve). | ||
|- | |- | ||
|||''SolverAlgorithm''|| | |||''SolverAlgorithm''||Description of method used. | ||
|- | |- | ||
|||''x_0''||Starting point. | |||''x_0''||Starting point. | ||
|- | |-valign="top" | ||
|||''xState''||State of each variable, described in [[TOMLAB Appendix B]]. | |||''xState''||State of each variable, described in [[TOMLAB Appendix B#Table:_The_state_variable_xState_for_the_variable.|TOMLAB Appendix B]]. | ||
|- | |-valign="top" | ||
|||''mipSolve''||A structure with warm start information. Use with WarmDefGLOBAL, see [[MipSolve#Warm_Start|example]]. | |||''mipSolve''||A structure with warm start information. Use with WarmDefGLOBAL, see [[MipSolve#Warm_Start|example]]. | ||
|- | |- |
Latest revision as of 03:54, 20 August 2013
Purpose
Solve mixed-integer linear programming problems (MIP).
mipSolve solves problems of the form
where , and .The variables , the index subset of are restricted to beintegers.
Starting with TOMLAB version 4.0, mipSolve accepts upper and lower bounds on the linear constraints like most other TOMLAB solvers. Thus it is no longer necessary to use slack variables to handle inequality constraints.
Calling Syntax
Recommended is to first set IterPrint, to get information each iteration
Prob.optParam.IterPrint = 1;
Driver call, including printing with level 2:
Result = tomRun('mipSolve',Prob,2)
Direct solver call:
Result = mipSolve(Prob);
PrintResult(Result);
Warm Start
To make a restart (warm start), just set the warm start flag, and call mipSolve once again:
Prob.WarmStart = 1;
Result = tomRun('mipSolve', Prob, ...);
mipSolve will read warm start information from the mipSolveSave.mat file.
Another warm start (with same MaxFunc) is made by just calling tomRun again.
Result = tomRun('mipSolve', Prob, ...);
To make a restart from the warm start information in the Result structure, make a call to WarmDefGLOBAL before calling mipSolve. WarmDefGLOBAL moves information from the Result structure to the Prob structure and sets the warm start flag, Prob.WarmStart = 1;
Prob = WarmDefGLOBAL('mipSolve', Prob, Result);
where Result is the result structure returned by the previous run. A warm start (with same MaxIter) is done by just calling tomRun again
Result = tomRun('mipSolve', Prob, ...);
To make another warm start with new MaxIter 100, say, redefine MaxIter as:
Prob.optParam.MaxIter = 100;
Then repeat the two lines:
Prob = WarmDefGLOBAL('mipSolve', Prob, Result);
Result = tomRun('mipSolve', Prob, ...);
Inputs
Prob | Problem description structure. The following fields are used: | |
---|---|---|
c | The vector c in cTx. | |
A | Constraint matrix for linear constraints. | |
b_L | Lower bounds on the linear constraints. If empty, Prob.b_U is used. | |
b_U | Upper bounds on the linear constraints. | |
x_L | Lower bounds on the variables. | |
x_U | Upper bounds on the variables. | |
x_0 | Starting point. | |
MaxCPU | Maximal CPU Time (in seconds) to be used by mipSolve, stops with best point found. | |
PriLevOpt | Print level in sub-solver, see the documentation for the solver. | |
PriLev | Print level in mipSolve (default 1). Also see optParam.IterPrint. | |
WarmStart | If true, >0, mipSolve reads the output from the last run from Prob.mipSolve, if it exists. If it doesn't exist, mipSolve attempts to open and read warm start data from mat-file mipSolveSave.mat. mipSolve uses the warm start information to continue from the last run. The mat-file mipSolveSave.mat is saved every Prob.MIP.SaveFreq iteration | |
QP.B | Active set B_0 at start: B(i) = 1: Include variable x(i) is in basic set. B(i) = 0: Variable x(i) is set on its lower bound. B(i) = -1: Variable x(i) is set on its upper bound. | |
SolverLP | Name of the solver used for the initial LP subproblem. If empty, the best available solver with a license is picked from a list. Note - If using MINOS, use the special LP interface LP-MINOS | |
SolverDLP | Name of the solver used for dual LP subproblems. If empty, SolverLP is used. If SolverLP/SolverDLP is a SOL solver (SNOPT, MINOS or NPSOL), the SOL.optPar and SOL.PrintFile is used: See help minosTL.m, npsolTL.m or snoptTL.m for how to set these parameters. | |
MIP | Structure in Prob, Prob.MIP. Defines integer optimization parameters: | |
MIP.IntVars | If empty, all variables are assumed non-integer. If islogical(IntVars) (i.e. all elements are 0/1), then 1 = integer variable, 0 = continuous variable. If any element >1, IntVars is the indices for integer variables | |
MIP.VarWeight | Weight for each variable in the variable selection phase. A lower value gives higher priority. Setting Prob.MIP.VarWeight = c; for knapsack problems improve convergence. | |
MIP.DualGap | mipSolve stops if the duality gap is less than DualGap. E.g. DualGap = 1, implies a stop at the first integer solution. E.g. DualGap = 0.01, stop if the solution less than one percent from the optimal solution. | |
MIP.fIP | An upper bound on the IP value wanted. Makes it possible to cut branches and avoid node computations. Used even if xIP not given. | |
MIP.xIP | The x-value giving the fIP value, if a solution (xIP, fIP) is known. | |
MIP.NodeSel | Node selection method: 0: Depth first. Priority on nodes with more integer components. 1: Breadth first. Priority on nodes with more integer components. 2: Depth first. When integer solution found, use NodeSel = 1 (Default). 3: Pure LIFO (Last in, first out) Depth First 4: Pure FIFO (First in, first out) Breadth First 5: Pure LIFO Depth First. When integer solution found, use NodeSel = 4. | |
MIP.VarSel | Variable selection method in branch and bound. 1: Use variable with most fractional value 2: Use gradient and distance to nearest integer value | |
MIP.KNAPSACK | If solving a knapsack problem, set to true (1) to use a knapsack heuristic. | |
MIP.ROUNDH | If = 1, use a rounding heuristic. Default 1. | |
MIP.SaveFreq | Warm start info saved on mipSolveSave.mat every SaveFreq iteration. (default -1, i.e. no warm start info is saved) | |
Solver | Options for the LP subproblem: | |
Solver.method | Rule to select new variables in DualSolve/lpSimplex: 0: Minimum reduced cost, sort variables increasing (default). 1: Bland's Anti-Cycling Rule 2: Minimum reduced cost. Dantzig's rule. | |
optParam | Structure in Prob. Fields used in Prob.optParam, also in sub-solvers: | |
optParam.MaxIter | Maximal number of iterations. max(10*dim(x),100) is default. | |
optParam.IterPrint | Print short information each iteration (PriLev > 0 ==> IterPrint = 1). One line each iteration with: Iteration number | |
optParam.bTol | Linear constraint violation convergence tolerance | |
Fields in Prob.optParam that are used by lpSimplex and DualSolve (assuming they are set as sub-solvers): | ||
optParam.eps_f | Tolerance used for function value tests | |
optParam.eps_Rank | Rank tolerance |
Outputs
Result | Structure with result from optimization. The following fields are changed: | |
---|---|---|
Iter | Number of iterations. | |
ExitFlag | ExitFlag. 0: Global optimal solution found, or integer solution with duality gap less than user tolerance. 1: Maximal number of iterations reached. 2: Empty feasible set, no integer solution found. 3: Rank problems (not used). 4: No feasible point found running LP relaxation. 5: Illegal x_0 found in LP relaxation. 99: Maximal CPU Time used (cputime > Prob.MaxCPU). | |
ExitText | Text string giving ExitFlag and Inform information. | |
Inform | If ExitFlag > 0, Inform = ExitFlag, except if duality gap less than given tolerance (Inform = 6) | |
DualGap | Relative duality gap, max(0, fIPMin-fLB)/|fIPMin|, if fIPMin ~=0; max(0,fIPMin-fLB) if fIPMin == 0. If fIPMin ~=0: Scale with 100, 100*DualGap, to get the percentage duality gap. For absolute value duality gap: scale with fIPMin, fIPMin * DualGap | |
x_k | Solution. | |
v_k | Lagrange parameters (n+m) vector, [Bounds(n); Linear constraints (m)]. | |
QP.B | B Optimal set. B(i)==0 implies inclusion of variable x(i) in basic set. sum(B==1)==length(b) holds. See QP.B as input. | |
QP.y | Dual parameters y (also part of Result.v_k). | |
f_k | Function value cTx_k, fIPMin (Best integer feasible solution). | |
g_k | Gradient value at optimum, c. | |
Solver | Solver used (mipSolve). | |
SolverAlgorithm | Description of method used. | |
x_0 | Starting point. | |
xState | State of each variable, described in TOMLAB Appendix B. | |
mipSolve | A structure with warm start information. Use with WarmDefGLOBAL, see example. | |
Prob | Problem structure used. |
Description
The routine mipSolve is an implementation of a branch and bound algorithm. mipSolve normally uses the linear programming routines lpSimplex and DualSolve to solve relaxed subproblems. mipSolve calls the general interface routines SolveLP and SolveDLP. By changing the setting of the structure fields Prob.Solver.SolverLP and Prob.Solver.SolverDLP, different sub-solvers are possible to use, see the help for the interface routines.
Algorithm
See mipSolve.m.
Examples
See exip39, exknap, expkorv.
M-files Used
lpSimplex.m, DualSolve.m, GetSolver.m, tomSolve.m
See Also
- cutPlane
- balas
- solveLP
- solveDLP