The OPTMILP Procedure

Overview: OPTMILP Procedure

The OPTMILP procedure is a solver for general 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 OPTMILP 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 OPTMILP procedure also implements advanced techniques such as presolving, generating cutting planes, and applying primal heuristics to improve the efficiency of the overall algorithm.

The OPTMILP procedure requires a mixed integer linear program to be specified using a SAS data set that adheres to the mathematical programming system (MPS) format, a widely accepted format in the optimization community. Chapter 17 discusses the MPS format in detail. It is also possible to input an incumbent solution in MPS format; see the section Warm Start for details.

You can use the MPSOUT= option to convert data sets that are formatted for the LP procedure into MPS-format SAS data sets. The option is available in the LP, INTPOINT, and NETFLOW procedures. For details about this option, see Chapter 5: The LP Procedure in SAS/OR 13.2 User's Guide: Mathematical Programming Legacy Procedures, Chapter 4: The INTPOINT Procedure in SAS/OR 13.2 User's Guide: Mathematical Programming Legacy Procedures, and Chapter 6: The NETFLOW Procedure in SAS/OR 13.2 User's Guide: Mathematical Programming Legacy Procedures.

The OPTMILP procedure provides various control options and solution strategies. In particular, you can enable, disable, or set levels for the advanced techniques previously mentioned.

The OPTMILP procedure outputs an optimal solution or the best feasible solution found, if any, in SAS data sets. This enables you to generate solution reports and perform additional analyses by using SAS software.