The Mixed Integer Linear Programming Solver

Overview: MILP Solver

The OPTMODEL procedure provides a framework for specifying and solving mixed integer linear programs (MILPs). A standard mixed integer linear program has the formulation

$\begin{array}{rlr} \displaystyle \mathop {\min } & \mathbf{c}^{T} \mathbf{x} & \\ \mbox{subject to} & \mathbf{A} \mathbf{x}\; \{ \ge , =, \le \} \; \mathbf{b} & ~ ~ ~ ~ ~ ~ ~ \mr{(MILP)}\\ & \mathbf{l} \le \mathbf{x} \le \mathbf{u} & \\ & \mathbf{x}_ i \in \mathbb {Z}~ ~ ~ \forall i \in \mathcal{S} & \end{array}$

where

$\mathbf{x}$	$\in$	$\mathbb {R}^{n}$	is the vector of structural variables
$\mathbf{A}$	$\in$	$\mathbb {R}^{m \times n}$	is the matrix of technological coefficients
$\mathbf{c}$	$\in$	$\mathbb {R}^{n}$	is the vector of objective function coefficients
$\mathbf{b}$	$\in$	$\mathbb {R}^{m}$	is the vector of constraints right-hand sides (RHS)
$\mathbf{l}$	$\in$	$\mathbb {R}^{n}$	is the vector of lower bounds on variables
$\mathbf{u}$	$\in$	$\mathbb {R}^{n}$	is the vector of upper bounds on variables
${\mathcal S}$			is a nonempty subset of the set $\{ 1 \dots ,n\}$ of indices

The MILP solver, available in the OPTMODEL procedure, implements a linear-programming-based branch-and-cut algorithm. This divide-and-conquer approach attempts to solve the original problem by solving linear programming relaxations of a sequence of smaller subproblems. The MILP solver also implements advanced techniques such as presolving, generating cutting planes, and applying primal heuristics to improve the efficiency of the overall algorithm.

The MILP solver provides various control options and solution strategies. In particular, you can enable, disable, or set levels for the advanced techniques previously mentioned. It is also possible to input an incumbent solution; see the section Warm Start Option for details.