PROC LP (SAS/OR Software)

Linear, integer, and mixed-integer programming

The LP procedure solves linear, integer, and mixed-integer programming problems and provides interactive control of the solution process and printing.  It  handles both sparse and dense data input formats and enables you to perform ranging, objective, and right-hand-side sensitivity analysis and parametric programming. In addition, the software saves intermediate results for "warm-starts."  PROC LP can be used interactively as well as in batch mode.

PROC LP is part of SAS/OR Software, a fully-integrated component of the SAS System, and uses SAS data sets (proprietary format) for input and output.  By taking advantage of the SAS System's Multiple Engine Architecture, PROC LP can in effect read from and write to over fifty different database formats.  

In addition to producing output SAS data sets, PROC LP can print text output detailing the characteristics of the problem solved, the solution path, variable and constraint information at the final solution, and any applicable information on sensitivity analysis or infeasibility.  For integer and mixed-integer programs, PROC LP prints a report of the branch and bound iterations. 

Input Data

• model data set can be specified in either a dense or sparse format
  • the sparse format is more flexible than the MPS format, but is consistent with the MPS input format
  • an available macro can convert a mathematical program from the CONVERT format as specified in the IBM MPSX Program Description Manual to the sparse format of PROC LP
• primal data set can be input to warm-start the solution process, using a previous solution

Output Data

• primal data set contains the primal solution, including the basic and nonbasic variable names, their values in the solution, cost coefficients, and reduced costs
• dual data set contains the dual solution, including the values of the constraints and the dual values
• active data set contains a representation of the current state of the branch and bound tree for restarting mixed-integer programs
• macro status variable saved for easier system integration

Integer Features

• save and restart mixed-integer problems
• numerous options for controlling the generation and search of the branch and bound tree
• program algorithm modification during tree search

Algorithms

• revised simplex algorithm with LU factorization of the basis (Bartels, 1971)
• branch and bound algorithm for integer variables
• sparse column representation to reduce memory needs and limit arithmetic computation
• crash routine to identify advanced starting basis
• special ordered sets
• numerous pricing algorithms to choose from (Greenberg, 1978)

Special Features

• goal programming (Ignizio, 1976)
• specify, solve, and analyze several related mathematical programs by supplying multiple right-hand-sides and/or objective functions

Post-Optimality Analysis

• right-hand-side and price sensitivity analysis
• right-hand-side and price ranging

Interactive Features

• interactive and programmed interruption of iterations
  • reset procedure options
  • provide single step or multiple step processing
  • print intermediate results
  • perform post-optimality analysis

Problem Size Limitations

The size of a problem that PROC LP can solve depends on the host platform, the available memory, and the available space for utility data sets.   PROC LP does not place any additional limits on problem size. 

Available Platforms

The SAS System is supported on all major personal computer, workstation, and mainframe operating systems.

Need more info?

Visit SAS Institute Research & Development on the WWW or contact:

SAS Institute Inc. 
SAS Campus Drive 
Cary, NC 27513 
Phone: (919) 677-8000
Fax: (919) 677-4444
Email: saseph@unx.sas.com

References

R. Bartels (1971), "A Stabilization of the Simplex Method," Numerical Mathematics, 16, 414-434.

H.J. Greenberg (ed.)(1978),  "Pivot Selection Tactics," in Design and Implementation of Optimization Software, Sijthoff & Noordhoff, Netherlands.

J.P. Ignizio (1976), Goal Programming and Extensions, D.C. Heath and Company, Lexington, Massachusetts.

[ Optimization Software Guide | OTC Home Page | NEOS Server | NEOS Guide ]