The Linear Programming Solver

Overview: LP Solver

The OPTMODEL procedure provides a framework for specifying and solving linear programs (LPs). A standard linear program has the following formulation:

$\begin{array}{rl} \displaystyle \mathop {\min } & \mathbf{c}^\mr {T} \mathbf{x} \\ \mbox{subject to} & \mathbf{A} \mathbf{x}\; \{ \ge , =, \le \} \; \mathbf{b} \\ & \mathbf{l} \le \mathbf{x} \le \mathbf{u} \end{array}$

where

$\mathbf{x}$	$\in$	$\mathbb {R}^{n}$	is the vector of decision variables
$\mathbf{A}$	$\in$	$\mathbb {R}^{m \times n}$	is the matrix of constraints
$\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

The following LP algorithms are available in the OPTMODEL procedure:

primal simplex algorithm
dual simplex algorithm
network simplex algorithm
interior point algorithm

The primal and dual simplex algorithms implement the two-phase simplex method. In phase I, the algorithm tries to find a feasible solution. If no feasible solution is found, the LP is infeasible; otherwise, the algorithm enters phase II to solve the original LP. The network simplex algorithm extracts a network substructure, solves this using network simplex, and then constructs an advanced basis to feed to either primal or dual simplex. The interior point algorithm implements a primal-dual predictor-corrector interior point algorithm. If any of the decision variables are constrained to be integer-valued, then the relaxed version of the problem is solved.