The LP Procedure

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.