CutPlane: Difference between revisions
(Created page with "==Purpose== Solve mixed integer linear programming problems (MIP). ''cutplane ''solves problems of the form <math> \begin{array}{ccccccl} \min\limits_{x} & f(x) & = & c^{T}...") |
No edit summary |
||
(4 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
[[Category:Solvers]] | |||
==Purpose== | ==Purpose== | ||
Line 8: | Line 9: | ||
<math> | <math> | ||
\begin{array}{ccccccl} | \begin{array}{ccccccl} | ||
\min\limits_{x} & f(x) & = & c^{T}x & & \\\mbox{subject to} & 0 & \leq & x & \leq & x_{U} & \\& & & Ax & = & b, & ~x_{j} \in \ | \min\limits_{x} & f(x) & = & c^{T}x & & \\\mbox{subject to} & 0 & \leq & x & \leq & x_{U} & \\& & & Ax & = & b, & ~x_{j} \in \mathbb{N}\, \forall j \in I \\ | ||
\end{array} | \end{array} | ||
</math> | </math> | ||
where <math> | where <math>c, x, x_U \in \mathbb{R}^{n}</math>, <math>A\in \mathbb{R}^{m\times | ||
n} | n}</math> and <math>b \in \mathbb{R}^{m}</math>. The variables <math>x \in I</math>, the index | ||
subset of <math> | subset of <math>1,...,n</math> are restricted to be integers. | ||
==Calling Syntax== | ==Calling Syntax== | ||
<source lang="matlab"> | |||
Result = cutplane(Prob); or | Result = cutplane(Prob); or | ||
Result = tomRun('cutplane', Prob); | Result = tomRun('cutplane', Prob); | ||
</source> | |||
==Description of Inputs== | |||
{| | {| class="wikitable" | ||
!''Prob'' | |||
!colspan="2"|Problem description structure. The following fields are used: | |||
|- | |- | ||
|||''c''||Constant vector. | |||''c''||Constant vector. | ||
Line 41: | Line 43: | ||
|- | |- | ||
|||''x_0''||Starting point. | |||''x_0''||Starting point. | ||
|- | |-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'') in basic set. | |||
''B''(''i'') = 0: Variable ''x''(''i'') is set on it's lower bound. | |||
''B''(''i'') = ''-''1: Variable ''x''(''i'') is set on it's upper bound. | |||
''B ''empty: ''lpSimplex ''solves Phase I LP to find a feasible point. | |||
|- | |-valign="top" | ||
|||''Solver.Method''||Variable selection rule to be used: | |||''Solver.Method''||Variable selection rule to be used: | ||
0: Minimum reduced cost. (default) | |||
1: Bland's anti-cycling rule. | |||
2: Minimum reduced cost, Dantzig's rule. | |||
|- | |- | ||
|||''MIP.IntVars''||Which of the ''n ''variables are integers. | |||''MIP.IntVars''||Which of the ''n ''variables are integers. | ||
|- | |- | ||
|||''SolverLP''||Name of the solver used for initial | |||''SolverLP''||Name of the solver used for initial LP subproblem. | ||
|- | |- | ||
|||''SolverDLP''||Name of the solver used for dual LP subproblems. | |||''SolverDLP''||Name of the solver used for dual LP subproblems. | ||
|- | |-valign="top" | ||
|||''optParam''||Structure with special fields for optimization parameters, | |||''optParam''||Structure with special fields for optimization parameters, see [[TOMLAB Appendix A]]. | ||
Fields used are: ''MaxIter'', ''PriLev'', ''wait'', ''eps_f'', ''eps_Rank'', ''xTol'' and ''bTol''. | |||
|} | |} | ||
==Description of Outputs== | |||
{| | |||
{|class="wikitable" | |||
!''Result'' | |||
!colspan="2"|Structure with result from optimization. The following fields are changed: | |||
|- | |- | ||
|||''x_k''||Optimal point. | |||''x_k''||Optimal point. | ||
Line 79: | Line 83: | ||
|||''f_k''||Function value at optimum. | |||''f_k''||Function value at optimum. | ||
|- | |- | ||
|||''g_k ''||Gradient value at optimum, ''c''. | |||''g_k''||Gradient value at optimum, ''c''. | ||
|- | |- | ||
|||''v_k''||Lagrange multipliers. | |||''v_k''||Lagrange multipliers. | ||
Line 96: | Line 100: | ||
|- | |- | ||
|||''ConstrEv''||Number of constraint evaluations. Equal to ''Iter''. | |||''ConstrEv''||Number of constraint evaluations. Equal to ''Iter''. | ||
|- | |-valign="top" | ||
|||''ExitFlag''||0: OK. | |||''ExitFlag''||0: OK. | ||
1: Maximal number of iterations reached. | |||
4: No feasible point ''x 0 ''found. | |||
|- | |- | ||
|||''Inform''||If ''ExitFlag > ''0, ''Inform ''= ''ExitFlag''. | |||''Inform''||If ''ExitFlag > ''0, ''Inform ''= ''ExitFlag''. | ||
Line 114: | Line 118: | ||
==Description== | ==Description== | ||
The routine ''cutplane ''is an implementation of a cutting plane algorithm with Gomorov cuts. ''cutplane ''normally uses the linear programming routines ''lpSimplex ''and ''DualSolve ''to solve relaxed subproblems. By changing the setting of the structure fields ''Prob.Solver.SolverLP ''and ''Prob.Solver.SolverDLP'', different sub-solvers are possible to use. | The routine ''cutplane'' is an implementation of a cutting plane algorithm with Gomorov cuts. ''cutplane ''normally uses the linear programming routines ''lpSimplex ''and ''DualSolve ''to solve relaxed subproblems. By changing the setting of the structure fields ''Prob.Solver.SolverLP ''and ''Prob.Solver.SolverDLP'', different sub-solvers are possible to use. | ||
''cutplane ''can interpret ''Prob.MIP.IntVars ''in two different ways: | ''cutplane'' can interpret ''Prob.MIP.IntVars'' in two different ways: | ||
*Vector of length less than dimension of problem: the elements designate indices of integer variables, e.g. <math> | *Vector of length less than dimension of problem: the elements designate indices of integer variables, e.g. <math>IntVars = [1\; 3\; 5]</math> restricts <math>x_1,x_3</math> and <math>x_5</math> to take integer values only. | ||
*Vector of same length as <math> | *Vector of same length as <math>c</math>: non-zero values indicate integer variables, e.g. with five variables (<math>x\in \mathbb{R}^5</math> ), <math>IntVars=[ 1\; 1\; 0\; 1\; 1 ]</math> demands all but <math>x_3</math> to take integer values. | ||
==M-files Used== | ==M-files Used== | ||
Line 128: | Line 132: | ||
==See Also== | ==See Also== | ||
mipSolve, balas, lpsimpl, lpsimp2, lpdual, tomSolve. |
Latest revision as of 08:09, 10 January 2012
Purpose
Solve mixed integer linear programming problems (MIP).
cutplane solves problems of the form
where , and . The variables , the index
subset of are restricted to be integers.
Calling Syntax
Result = cutplane(Prob); or
Result = tomRun('cutplane', Prob);
Description of Inputs
Prob | Problem description structure. The following fields are used: | |
---|---|---|
c | Constant vector. | |
A | Constraint matrix for linear constraints. | |
b_L | Lower bounds on the linear constraints. | |
b_U | Upper bounds on the linear constraints. | |
x_L | Lower bounds on the variables (assumed to be 0). | |
x_U | Upper bounds on the variables. | |
x_0 | Starting point. | |
QP.B | Active set B_0 at start:
B(i) = 1: Include variable x(i) in basic set. B(i) = 0: Variable x(i) is set on it's lower bound. B(i) = -1: Variable x(i) is set on it's upper bound. B empty: lpSimplex solves Phase I LP to find a feasible point. | |
Solver.Method | Variable selection rule to be used:
0: Minimum reduced cost. (default) 1: Bland's anti-cycling rule. 2: Minimum reduced cost, Dantzig's rule. | |
MIP.IntVars | Which of the n variables are integers. | |
SolverLP | Name of the solver used for initial LP subproblem. | |
SolverDLP | Name of the solver used for dual LP subproblems. | |
optParam | Structure with special fields for optimization parameters, see TOMLAB Appendix A.
Fields used are: MaxIter, PriLev, wait, eps_f, eps_Rank, xTol and bTol. |
Description of 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. | |
QP.B | Optimal active set. See input variable QP.B. | |
xState | State of each variable, described in Table 150 . | |
x_0 | Starting point. | |
f_0 | Function value at start. | |
Iter | Number of iterations. | |
FuncEv | Number of function evaluations. Equal to Iter. | |
ConstrEv | Number of constraint evaluations. Equal to Iter. | |
ExitFlag | 0: OK.
1: Maximal number of iterations reached. 4: No feasible point x 0 found. | |
Inform | If ExitFlag > 0, Inform = ExitFlag. | |
Solver | Solver used. | |
SolverAlgorithm | Solver algorithm used. | |
Prob | Problem structure used. |
Description
The routine cutplane is an implementation of a cutting plane algorithm with Gomorov cuts. cutplane normally uses the linear programming routines lpSimplex and DualSolve to solve relaxed subproblems. By changing the setting of the structure fields Prob.Solver.SolverLP and Prob.Solver.SolverDLP, different sub-solvers are possible to use.
cutplane can interpret Prob.MIP.IntVars in two different ways:
- Vector of length less than dimension of problem: the elements designate indices of integer variables, e.g. restricts and to take integer values only.
- Vector of same length as : non-zero values indicate integer variables, e.g. with five variables ( ), demands all but to take integer values.
M-files Used
lpSimplex.m, DualSolve.m
See Also
mipSolve, balas, lpsimpl, lpsimp2, lpdual, tomSolve.