The LP Procedure
- Overview
-
Getting Started
-
Syntax
-
Details
Missing Values Dense Data Input Format Sparse Data Input Format Converting Any PROC LP Format to an MPS-Format SAS Data Set Converting Standard MPS Format to Sparse Format The Reduced Costs, Dual Activities, and Current Tableau Macro Variable ORLP Pricing Scaling Preprocessing Integer Programming Sensitivity Analysis Range Analysis Parametric Programming Interactive Facilities Memory Management Output Data Sets Input Data Sets Displayed Output ODS Table and Variable Names Memory Limit
-
Examples
An Oil Blending Problem A Sparse View of the Oil Blending Problem Sensitivity Analysis: Changes in Objective Coefficients Additional Sensitivity Analysis Price Parametric Programming for the Oil Blending Problem Special Ordered Sets and the Oil Blending Problem Goal-Programming a Product Mix Problem A Simple Integer Program An Infeasible Problem Restarting an Integer Program Alternative Search of the Branch-and-Bound Tree An Assignment Problem A Scheduling Problem A Multicommodity Transshipment Problem with Fixed Charges Converting to an MPS-Format SAS Data Set Migration to OPTMODEL: Assignment Migration to OPTMODEL: Multicommodity Transshipment
- References
| Memory Management |
There are no restrictions on the problem size in the LP procedure. The number of constraints and variables in a problem that PROC LP can solve depends on the host platform, the available memory, and the available disk space for utility data sets.
Memory usage is affected by a great many factors including the density of the technological coefficient matrix, the model structure, and the density of the decomposed basis matrix. The algorithm requires that the decomposed basis fit completely in memory. Any additional memory is used for nonbasic columns. The partition between the decomposed basis and the nonbasic columns is dynamic so that as the inverse grows, which typically happens as iterations proceed, more memory is available to it and less is available for the nonbasic columns.
The LP procedure determines the initial size of the decomposed basis matrix. If the area used is too small, PROC LP must spend time compressing this matrix, which degrades performance. If PROC LP must compress the decomposed basis matrix on the average more than 15 times per iteration, then the size of the memory devoted to the basis is increased. If the work area cannot be made large enough to invert the basis, an error return occurs. On the other hand, if PROC LP compresses the decomposed basis matrix on the average once every other iteration, then memory devoted to the decomposed basis is decreased, freeing memory for the nonbasic columns.
For many models, memory constraints are not a problem because both the decomposed basis and all the nonbasic columns will have no problem fitting. However, when the models become large relative to the available memory, the algorithm tries to adjust memory distribution in order to solve the problem. In the worst cases, only one nonbasic column fits in memory with the decomposed basis matrix.
Problems involving memory use can occur when solving mixed-integer problems. Data associated with each node in the branch-and-bound tree must be kept in memory. As the tree grows, competition for memory by the decomposed basis, the nonbasic columns, and the branch-and-bound tree may become critical. If the situation becomes critical, the procedure automatically switches to branching strategies that use less memory. However, it is possible to reach a point where no further processing is possible. In this case, PROC LP terminates on a memory error.