CutPlane
Purpose
Solve mixed integer linear programming problems (MIP).
cutplane solves problems of the form
Failed to parse (unknown function "\MATHSET"): {\displaystyle \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 \MATHSET{N}\, \forall j \in $I$ \\ \end{array} }
where Failed to parse (unknown function "\MATHSET"): {\displaystyle $c, x, 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 \in \MATHSET{R}^{m}$}
. 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 Table 141. | |
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 (Failed to parse (unknown function "\MATHSET"): {\displaystyle $x\in \MATHSET{R}^5$} ), demands all but to take integer values.
M-files Used
lpSimplex.m, DualSolve.m