MipSolve: Difference between revisions
No edit summary |
No edit summary |
||
Line 1: | Line 1: | ||
[[Category:Solvers]] | [[Category:Solvers]] | ||
==Purpose== | ==Purpose== | ||
Line 22: | Line 20: | ||
==Calling Syntax== | ==Calling Syntax== | ||
<syntaxhighlight lang="matlab"> | |||
Result = tomRun('mipSolve',Prob,...) | Result = tomRun('mipSolve',Prob,...) | ||
</syntaxhighlight> | |||
===Description of Inputs=== | ===Description of Inputs=== | ||
{| | {| class="wikitable" | ||
|''Prob''||colspan="2"|Problem description structure. The following fields are used: | |''Prob''||colspan="2"|Problem description structure. The following fields are used: | ||
|- | |- | ||
|||''c''||The vector ''c ''in < | |||''c''||The vector ''c ''in ''c<sup>T</sup>x''. | ||
|- | |- | ||
|||''A ''||Constraint matrix for linear constraints. | |||''A ''||Constraint matrix for linear constraints. | ||
Line 44: | Line 44: | ||
|-valign="top" | |-valign="top" | ||
|||''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" | ||
|||''QP.B''||Active set ''B 0 ''at start: | |||''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 solver used for initial LP subproblem. Default solver is used if empty, see ''GetSolver.m ''and ''tomSolve.m''. | |||''SolverLP''||Name of solver used for initial LP subproblem. Default solver is used if empty, see ''GetSolver.m ''and ''tomSolve.m''. | ||
|-valign="top" | |-valign="top" | ||
|||''SolverDLP''||Name of solver used for the dual LP subproblems. Default solver is used if empty, see ''GetSolver.m ''and ''tomSolve.m''. | |||''SolverDLP''||Name of solver used for the dual LP subproblems. Default solver is used if empty, see ''GetSolver.m ''and ''tomSolve.m''. | ||
|- | |-valign="top" | ||
|||''PriLevOpt ''||Print level in ''lpSimplex ''and ''DualSolve'': | |||''PriLevOpt ''||Print level in ''lpSimplex ''and ''DualSolve'': | ||
0: No output; ''> ''0: Convergence result; | |||
> ''1: Output every iteration; ''> ''2: Output each step in simplex algorithm. | |||
|- | |- | ||
|||''PriLev''||Print level in ''mipSolve''. | |||''PriLev''||Print level in ''mipSolve''. | ||
Line 70: | Line 70: | ||
|- | |- | ||
|||''MIP''||Structure with fields for integer optimization The following fields are used: | |||''MIP''||Structure with fields for integer optimization The following fields are used: | ||
|- | |-valign="top" | ||
|||''IntVars''||The set of integer variables. | |||''IntVars''||The set of integer variables. | ||
If empty, all variables are assumed non-integer (LP problem) | |||
|- | |-valign="top" | ||
|||''VarWeight''||Weight for each variable in the variable selection phase. | |||''VarWeight''||Weight for each variable in the variable selection phase. | ||
A lower value gives higher priority. Setting ''Prob.MIP.VarWeight ''= ''Prob.c'' improves convergence for knapsack problems. | |||
|- | |- | ||
|||''DualGap''||''mipSolve ''stops if the duality gap is less than ''DualGap''. To stop at the first found integer solution, set ''DualGap ''=1. For example, ''DualGap ''= 0.01 makes the algorithm stop if the solution is ''< ''1% from the optimal solution. | |||''DualGap''||''mipSolve ''stops if the duality gap is less than ''DualGap''. To stop at the first found integer solution, set ''DualGap ''=1. For example, ''DualGap ''= 0.01 makes the algorithm stop if the solution is ''< ''1% from the optimal solution. | ||
Line 87: | Line 87: | ||
|||''KNAPSACK''||If solving a knapsack problem, set to true (1) to use a knapsack heuristic. | |||''KNAPSACK''||If solving a knapsack problem, set to true (1) to use a knapsack heuristic. | ||
|- | |- | ||
|||''optParam''||Structure with special fields for optimization parameters, see | |||''optParam''||Structure with special fields for optimization parameters, see [[TOMLAB Appendix A]]. Fields used are: ''IterPrint'', ''MaxIter'', ''PriLev'', ''wait'', ''eps f ''and ''eps Rank''. | ||
|- | |- | ||
|||''Solver''||Structure with fields for algorithm choices: | |||''Solver''||Structure with fields for algorithm choices: | ||
|- | |-valign="top" | ||
|||''Alg''||Node selection method: | |||''Alg''||Node selection method: | ||
0: Depth first | |||
1: Breadth first | |||
2: Depth first. When integer solution found, switch to Breadth. | |||
|- | |-valign="top" | ||
|||''method''||Rule to select new variables in DualSolve/lpSimplex: | |||''method''||Rule to select new variables in DualSolve/lpSimplex: | ||
0: Minimum reduced cost, sort variables increasing. (Default) | |||
1: Bland's rule (default). | |||
2: Minimum reduced cost. Dantzig's rule. | |||
|} | |} | ||
== | ==Outputs== | ||
{| | {| class="wikitable" | ||
|-valign"top" | |-valign"top" | ||
|''Result''||colspan="2"|Structure with result from optimization. The following fields are changed: | |''Result''||colspan="2"|Structure with result from optimization. The following fields are changed: | ||
Line 120: | Line 120: | ||
|||''g_k''||Gradient value at optimum, ''c''. | |||''g_k''||Gradient value at optimum, ''c''. | ||
|- | |- | ||
|||''v_k''||Lagrange multipliers, | |||''v_k''||Lagrange multipliers, [Constraints + lower + upper bounds]. | ||
|- | |- | ||
|||''x_0''||Starting point. | |||''x_0''||Starting point. | ||
Line 126: | Line 126: | ||
|||''f_0''||Function value at start. | |||''f_0''||Function value at start. | ||
|- | |- | ||
|||''xState''||State of each variable, described in | |||''xState''||State of each variable, described in [[TOMLAB Appendix B]]. | ||
|- | |- | ||
|||''Inform''||If ''ExitF lag > ''0, ''I nf orm ''= ''ExitF lag''. | |||''Inform''||If ''ExitF lag > ''0, ''I nf orm ''= ''ExitF lag''. | ||
Line 137: | Line 137: | ||
|- | |- | ||
|||''alphaV''||Step lengths for each search step. | |||''alphaV''||Step lengths for each search step. | ||
|- | |-valign="top" | ||
|||''ExitFlag''||0: OK. | |||''ExitFlag''||0: OK. | ||
1: Maximal number of iterations reached. | |||
2: Empty feasible set, no integer solution found. | |||
3: Rank problems. Can not find any solution point. | |||
4: No feasible point found running LP relaxation. | |||
5: Illegal''x_0 ''found in LP relaxation. | |||
99: Maximal CPU Time used (cputime ''> ''Prob.MaxCPU). | |||
|- | |- | ||
|||''Iter''||Number of iterations. | |||''Iter''||Number of iterations. | ||
Line 163: | Line 163: | ||
==Description== | ==Description== | ||
The routine ''mipSolve ''is an implementation of a branch and bound algorithm | 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== | ==Algorithm== | ||
See | See ''mipSolve.m''. | ||
==Examples== | ==Examples== |
Revision as of 03:27, 21 July 2011
Purpose
Solve mixed integer linear programming problems (MIP).
mipSolve solves problems of the form
Failed to parse (unknown function "\multicolumn"): {\displaystyle \begin{array}{cccccc} \min\limits_{x} & f(x) & = & c^{T}x & \\s/t & x_{L} & \leq & x & \leq & x_{U} \\& b_{L} & \leq & Ax & \leq & b_{U} \\ & & & \multicolumn{3}{l}{x_{j} \in \MATHSET{N} \ \ \forall j \in $I$} \\ \end{array} }
where Failed to parse (unknown function "\MATHSET"): {\displaystyle c, x, x_L, x_U \in \MATHSET{R}^{n}}
, Failed to parse (unknown function "\MATHSET"): {\displaystyle A\in \MATHSET{R}^{m\times n}}
and Failed to parse (unknown function "\MATHSET"): {\displaystyle b_L, b_U \in\MATHSET{R}^{m}}
.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
Result = tomRun('mipSolve',Prob,...)
Description of 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. | |
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 solver used for initial LP subproblem. Default solver is used if empty, see GetSolver.m and tomSolve.m. | |
SolverDLP | Name of solver used for the dual LP subproblems. Default solver is used if empty, see GetSolver.m and tomSolve.m. | |
PriLevOpt | Print level in lpSimplex and DualSolve:
0: No output; > 0: Convergence result; > 1: Output every iteration; > 2: Output each step in simplex algorithm. | |
PriLev | Print level in mipSolve. | |
SOL.optPar | Parameters for the SOL solvers, if they are used as subsolvers. | |
SOL.PrintFile | Name of print file for SOL solvers, if they are used as subsolvers. | |
MIP | Structure with fields for integer optimization The following fields are used: | |
IntVars | The set of integer variables.
If empty, all variables are assumed non-integer (LP problem) | |
VarWeight | Weight for each variable in the variable selection phase.
A lower value gives higher priority. Setting Prob.MIP.VarWeight = Prob.c improves convergence for knapsack problems. | |
DualGap | mipSolve stops if the duality gap is less than DualGap. To stop at the first found integer solution, set DualGap =1. For example, DualGap = 0.01 makes the algorithm stop if the solution is < 1% from the optimal solution. | |
fIP | An upper bound on the IP value wanted. Makes it possible to cut branches and avoid node computations. | |
xIP | The x-value giving the fIP value. | |
KNAPSACK | If solving a knapsack problem, set to true (1) to use a knapsack heuristic. | |
optParam | Structure with special fields for optimization parameters, see TOMLAB Appendix A. Fields used are: IterPrint, MaxIter, PriLev, wait, eps f and eps Rank. | |
Solver | Structure with fields for algorithm choices: | |
Alg | Node selection method:
0: Depth first 1: Breadth first 2: Depth first. When integer solution found, switch to Breadth. | |
method | Rule to select new variables in DualSolve/lpSimplex:
0: Minimum reduced cost, sort variables increasing. (Default) 1: Bland's rule (default). 2: Minimum reduced cost. Dantzig's rule. |
Outputs
Result | Structure with result from optimization. The following fields are changed: | |
x_k | Optimal point. | |
f_k | Function value at optimum. | |
g_k | Gradient value at optimum, c. | |
v_k | Lagrange multipliers, [Constraints + lower + upper bounds]. | |
x_0 | Starting point. | |
f_0 | Function value at start. | |
xState | State of each variable, described in TOMLAB Appendix B. | |
Inform | If ExitF lag > 0, I nf orm = ExitF lag. | |
QP.B | Optimal active set. See input variable QP.B. | |
QP.y | Dual parameters y (also part of Result.v_k. | |
p_dx | Search steps in x. | |
alphaV | Step lengths for each search step. | |
ExitFlag | 0: OK.
1: Maximal number of iterations reached. 2: Empty feasible set, no integer solution found. 3: Rank problems. Can not find any solution point. 4: No feasible point found running LP relaxation. 5: Illegalx_0 found in LP relaxation. 99: Maximal CPU Time used (cputime > Prob.MaxCPU). | |
Iter | Number of iterations. | |
Solver | Solver used ('mipSolve'). | |
SolverAlgorithm | Text description of solver algorithm used. | |
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