CutPlane

Purpose

Solve mixed integer linear programming problems (MIP).

cutplane solves problems of the form

${\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 \mathbb {N} \,\forall j\in I\\\end{array}}$

where $c,x,x_{U}\in \mathbb {R} ^{n}$, $A\in \mathbb {R} ^{m\times n}$ and $b\in \mathbb {R} ^{m}$. The variables $x\in I$, the index subset of $1,...,n$ 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. $IntVars=[1\;3\;5]$ restricts $x_{1},x_{3}$ and $x_{5}$ to take integer values only.

• Vector of same length as $c$: non-zero values indicate integer variables, e.g. with five variables ($x\in \mathbb {R} ^{5}$ ), $IntVars=[1\;1\;0\;1\;1]$ demands all but $x_{3}$ to take integer values.

M-files Used

lpSimplex.m, DualSolve.m

See Also

mipSolve, balas, lpsimpl, lpsimp2, lpdual, tomSolve.