The OPTLP Procedure
Overview: OPTLP Procedure
The OPTLP procedure provides four methods of solving linear programs (LPs). A linear program has the following formulation:
where
 |
 |  | is the vector of decision variables |
 |
|  | is the matrix of constraints |
 |
|  | is the vector of objective function coefficients |
 |
|  | is the vector of constraints’ right-hand sides (RHS) |
 |
| | is the vector of lower bounds on variables |
 |
| | 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
sifting 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. The sifting algorithm is a simplex-based column-generation algorithm.
PROC OPTLP requires a linear program to be specified using a data table that adheres to the MPS format, a widely accepted format in the optimization community. For details about the MPS format see Chapter 8, The MPS-Format Data Table.