The LP Procedure
- Overview
-
Getting Started
-
Syntax
-
DetailsMissing ValuesDense Data Input FormatSparse Data Input FormatConverting Any PROC LP Format to an MPS-Format SAS Data SetConverting Standard MPS Format to Sparse FormatThe Reduced Costs, Dual Activities, and Current TableauMacro Variable _ORLP_PricingScalingPreprocessingInteger ProgrammingSensitivity AnalysisRange AnalysisParametric ProgrammingInteractive FacilitiesMemory ManagementOutput Data SetsInput Data SetsDisplayed OutputODS Table and Variable NamesMemory Limit
-
ExamplesAn Oil Blending ProblemA Sparse View of the Oil Blending ProblemSensitivity Analysis: Changes in Objective CoefficientsAdditional Sensitivity AnalysisPrice Parametric Programming for the Oil Blending ProblemSpecial Ordered Sets and the Oil Blending ProblemGoal-Programming a Product Mix ProblemA Simple Integer ProgramAn Infeasible ProblemRestarting an Integer ProgramAlternative Search of the Branch-and-Bound TreeAn Assignment ProblemA Scheduling ProblemA Multicommodity Transshipment Problem with Fixed ChargesConverting to an MPS-Format SAS Data SetMigration to OPTMODEL: AssignmentMigration to OPTMODEL: Multicommodity Transshipment
- References
Converting Standard MPS Format to Sparse Format
The MPS input format was introduced by IBM as a way of specifying data for linear and integer programs. Before you can solve a linear program specified in the MPS input format by using the LP procedure, the data must be converted to the sparse format of the LP procedure. If you want to solve a linear program specified in the sparse LP format by using the OPTLP procedure, you must convert the data into an MPS-format SAS data set. This section describes how to perform both conversions.
SASMPSXS is a SAS macro function that converts the standard MPS format to the sparse format of the LP procedure. The following is an example of the MPS format:
NAME EXAMPLE
* THIS IS DATA FOR THE PRODUCT MIX PROBLEM.
ROWS
N PROFIT
L STAMP
L ASSEMB
L FINISH
N CHNROW
N PRICE
COLUMNS
DESK STAMP 3.00000 ASSEMB 10.00000
DESK FINISH 10.00000 PROFIT 95.00000
DESK PRICE 175.00000
CHAIR STAMP 1.50000 ASSEMB 6.00000
CHAIR FINISH 8.00000 PROFIT 41.00000
CHAIR PRICE 95.00000
CABINET STAMP 2.00000 ASSEMB 8.00000
CABINET FINISH 8.00000 PROFIT 84.00000
CABINET PRICE 145.00000
BOOKCSE STAMP 2.00000 ASSEMB 7.00000
BOOKCSE FINISH 7.00000 PROFIT 76.00000
BOOKCSE PRICE 130.00000 CHNROW 1.00000
RHS
TIME STAMP 800.00000 ASSEMB 1200.0000
TIME FINISH 800.00000
RANGES
T1 ASSEMB 900.00000
BOUNDS
UP CHAIR 75.00000
LO BOOKCSE 50.00000
ENDATA
In this example, the company tries to find an optimal product mix of four items: a DESK, a CHAIR, a CABINET, and a BOOKCASE. Each item is processed in a stamping department (STAMP), an assembly department (ASSEMB), and a finishing department (FINISH). The time each item requires in each department is given in the input data. Because of resource limitations, each department has an upper limit on the time available for processing. Furthermore, because of labor constraints, the assembly department must work at least 300 hours. Finally, marketing tells you not to make more than 75 chairs, to make at least 50 bookcases, and to find the range over which the selling price of a bookcase can vary without changing the optimal product mix.
The SASMPSXS macro function uses MPSFILE='FILENAME' as an argument to read an MPS input file. It then converts the file and
saves the conversion to a default SAS data set, PROB. The FILENAME should include the path.
Running the following statements on the preceding example
%sasmpsxs(mpsfile='filename'); proc print data=prob; run;
produces the sparse input form of the LP procedure:
OBS _TYPE_ _COL_ _ROW1_ _COEF1_ _ROW2_ _COEF2_
1 *OW . .
2 FREE PROFIT . .
3 LE STAMP . .
4 LE ASSEMB . .
5 LE FINISH . .
6 FREE CHNROW . .
7 FREE PRICE . .
8 *OL MNS . .
9 DESK STAMP 3.0 ASSEMB 10
10 DESK FINISH 10.0 PROFIT 95
11 DESK PRICE 175.0 .
12 CHAIR STAMP 1.5 ASSEMB 6
13 CHAIR FINISH 8.0 PROFIT 41
14 CHAIR PRICE 95.0 .
15 CABINET STAMP 2.0 ASSEMB 8
16 CABINET FINISH 8.0 PROFIT 84
17 CABINET PRICE 145.0 .
18 BOOKCSE STAMP 2 ASSEMB 7
19 BOOKCSE FINISH 7 PROFIT 76
20 BOOKCSE PRICE 130 CHNROW 1
21 *HS . .
22 RHS TIME STAMP 800 ASSEMB 1200
23 RHS TIME FINISH 800 .
24 *AN ES . .
25 RANGE T1 ASSEMB 900 .
26 *OU DS . .
27 UPPERBDD CHAIR UP 75 .
28 LOWERBDD BOOKCSE LO 50 .
SASMPSXS recognizes four MPS row types: E, L, G, and N. It converts them into types EQ, LE, GE, and FREE. Since objective rows, price change rows and free rows all share the same type N in the MPS format, you need a DATA step to assign proper types to the objective rows and price change rows.
data;
set prob;
if _type_='free' and _row1_='profit' then _type_='max';
if _type_='free' and _row1_='chnrow' then _type_='pricesen';
run;
proc lp sparsedata;
run;
In the MPS format, the variable types include LO, UP, FX, FR, MI, and BV. The SASMPSXS macro converts them into types LOWERBD, UPPERBD, FIXED, UNRESTRICTED, -INFINITY, and BINARY, respectively. Occasionally, you may need to define your own variable types, in which case, you must add corresponding type handling entries in the SASMPSXS.SAS program and use the SAS %INCLUDE macro to include the file at the beginning of your program. The SASMPSXS macro function can be found in the SAS sample library. Information on the MPS format can be obtained from Murtagh (1981).
SASMPSXS can take no arguments, or it can take one or two arguments. If no arguments are present, SASMPSXS assumes that the
MPS input file has been saved to a SAS data set named RAW. The macro then takes information from that data set and converts it into the sparse form of the LP procedure. The RAW data set should have the following six variables:
data RAW;
infile ...;
input field1 $ 2-3 field2 $ 5-12
field3 $ 15-22 field4 25-36
field5 $ 40-47 field6 50-61;
...
run;
If the preceding MPS input data set has a name other than RAW, you can use MPSDATA=SAS-data-set as an argument in the SASMPSXS macro function. If you want the converted sparse form data set to have a name other than PROB, you can use LPDATA=SAS-data-set as an argument. The order of the arguments in the SASMPSXS macro function is not important.