The OPTLP Procedure

Overview: OPTLP Procedure

The OPTLP procedure provides four methods of solving linear programs (LPs). A 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 OPTLP 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.

PROC OPTLP requires a linear program to be specified using a SAS data set that adheres to the MPS format, a widely accepted format in the optimization community. For details about the MPS format see Chapter 17: The MPS-Format SAS Data Set.

You can use the MPSOUT= option to convert typical PROC LP format data sets 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.