MipSolve

Purpose

Solve mixed integer linear programming problems (MIP).

mipSolve solves problems of the form

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

where $c,x,x_{L},x_{U}\in \mathbb {R} ^{n}$ , $A\in \mathbb {R} ^{m\times n}$ and $b_{L},b_{U}\in \mathbb {R} ^{m}$.The variables $x\in I$ , the index subset of $1,...,n$ 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

See Also

• cutPlane
• balas
• solveLP
• solveDLP