Example 4.6 Solving an LP Problem with Data in MPS Format

In this example, PROC INTPOINT is ultimately used to solve an LP. But prior to that, there is SAS code that is used to read a MPS format file and initialize an input SAS data set. MPS was an optimization package developed for IBM computers many years ago and the format by which data had to be supplied to that system became the industry standard for other optimization software packages, including those developed recently. The MPS format is described in Murtagh (1981). If you have an LP which has data in MPS format in a file /your-directory/your-filename.dat, then the following SAS code should be run:

filename w '/your-directory/your-filename.dat';
data raw;
   infile w lrecl=80 pad;
   input field1 $ 2-3 field2 $ 5-12 field3 $ 15-22
         field4  25-36 field5 $ 40-47 field6 50-61;
   run;
%sasmpsxs;
data lp;
   set;
   if _type_="FREE" then _type_="MIN";
   if lag(_type_)="*HS" then _type_="RHS";
   run;
proc sort data=lp;
   by _col_;
   run;

proc intpoint
   arcdata=lp 
   condata=lp sparsecondata rhsobs=rhs grouped=condata
   conout=solutn  /* SAS data set for the optimal solution */
   bytes=20000000 
   nnas=1700 ncoefs=4000 ncons=700 
   printlevel2=2 memrep;
   run;

proc lp 
   data=lp sparsedata 
   endpause time=3600 maxit1=100000 maxit2=100000;
   run;
   show status;
   quit;

You will have to specify the appropriate path and file name in which your MPS format data resides.

SASMPSXS is a SAS macro provided within SAS/OR software. The MPS format resembles the sparse format of the CONDATA= data set for PROC INTPOINT. The SAS macro SASMPSXS examines the MPS data and transfers it into a SAS data set while automatically taking into account how the MPS format differs slightly from PROC INTPOINT’s sparse format.

The parameters NNAS=1700, NCOEFS=4000, and NCONS=700 indicate the approximate (overestimated) number of variables, coefficients and constraints this model has. You must change these to your problems dimensions. Knowing these, PROC INTPOINT is able to utilize memory better and read the data faster. These parameters are optional.

The PROC SORT preceding PROC INTPOINT is not necessary, but sorting the SAS data set can speed up PROC INTPOINT when it reads the data. After the sort, data for each column is grouped together. GROUPED=condata can be specified.

For small problems, presorting and specifying those additional options is not going to greatly influence PROC INTPOINT’s run time. However, when problems are large, presorting and specifying those additional options can be very worthwhile.

If you generate the model yourself, you will be familiar enough with it to know what to specify for the RHSOBS= parameter. If the value of the SAS variable in the COLUMN list is equal to the character string specified as the RHSOBS= option, the data in that observation is interpreted as right-hand-side data as opposed to coefficient data. If you do not know what to specify for the RHSOBS= option, you should first run PROC LP and optionally set MAXIT1=1 and MAXIT2=1. PROC LP will output a Problem Summary that includes the line

 
Rhs Variable    rhs-charstr

BYTES=20000000 is the size of working memory PROC INTPOINT is allowed.

The options PRINTLEVEL2=2 and MEMREP indicate that you want to see an iteration log and messages about memory usage. Specifying these options is optional.