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
| Pricing |
PROC LP performs multiple pricing when determining which variable will enter the basis at each pivot (Greenberg 1978). This heuristic can shorten execution time in many problems. The specifics of the multiple pricing algorithm depend on the value of the PRICETYPE= option. However, in general, when some form of multiple pricing is used, during the first iteration PROC LP places the PRICE= nonbasic columns yielding the greatest marginal improvement to the objective function in a candidate list. This list identifies a subproblem of the original. On subsequent iterations, only the reduced costs for the nonbasic variables in the candidate list are calculated. This accounts for the potential time savings. When either the candidate list is empty or the subproblem is optimal, a new candidate list must be identified and the process repeats. Because identification of the subproblem requires pricing the complete problem, an iteration in which this occurs is called a major iteration. A minor iteration is an iteration in which only the subproblem is to be priced.
The value of the PRICETYPE= option determines the type of multiple pricing that is to be used. The types of multiple pricing include partial suboptimization (PRICETYPE=PARTIAL), complete suboptimization (PRICETYPE=COMPLETE), and complete suboptimization with dynamically varying the value of the PRICE= option (PRICETYPE=DYNAMIC).
When partial suboptimization is used, in each minor iteration the nonbasic column in the subproblem yielding the greatest marginal improvement to the objective is brought into the basis and removed from the candidate list. The candidate list now has one less entry. At each subsequent iteration, another column from the subproblem is brought into the basis and removed from the candidate list. When there are either no remaining candidates or the remaining candidates do not improve the objective, the subproblem is abandoned and a major iteration is performed. If the objective cannot be improved on a major iteration, the current solution is optimal and PROC LP terminates.
Complete suboptimization is identical to partial suboptimization with one exception. When a nonbasic column from the subproblem is brought into the basis, it is replaced in the candidate list by the basic column that is leaving the basis. As a result, the candidate list does not diminish at each iteration.
When PRICETYPE=DYNAMIC, complete suboptimization is performed, but the value of the PRICE= option changes so that the ratio of minor to major iterations is within two units of the PRICE= option.
These heuristics can shorten execution time for small values of the PRICE= option. Care should be exercised in choosing a value from the PRICE= option because too large a value can use more time than if pricing were not used.