The LP Procedure

An Integer Programming Example

Subsections:

The following is a simple mixed-integer programming problem. Details can be found in Example 5.8 in the section Examples: LP Procedure.

   data;
      format _row_ $10.; 
      input _row_ $ choco gumdr ichoco igumdr _type_ $ _rhs_;
      datalines;
   object        .25    .75   -100    -75 max        .
   cooking        15     40      0      0 le     27000
   color           0  56.25      0      0 le     27000
   package     18.75      0      0      0 le     27000
   condiments     12     50      0      0 le     27000
   chocolate       1      0 -10000      0 le         0
   gum             0      1      0 -10000 le         0
   only_one        0      0      1      1 eq         1
   binary          .      .      1      2 binary     .
   ;

The row with 'binary' type indicates that this problem is a mixed-integer program and all the integer variables are binary. The integer values of the row set an ordering for PROC LP to pick the branching variable when VARSELECT=PRIOR is chosen. Smaller values will have higher priorities. The _ROW_ variable here is an alias of the _ID_ variable.

This problem can be solved with the following statements:

    proc lp canselect=lifo backtrack=obj varselect=far endpause;
    run;
    quit;
    %put &_orlp_; 

The options CANSELECT=, BACKTRACK=, and VARSELECT= specify the rules for picking the next active problem and the rule to choose the branching variable. In this example, the values LIFO, OBJ and FAR serve as the default values, so the three options can be omitted from the PROC LP statement. The following is the output from the %PUT statement:


STATUS=SUCCESSFUL PHASE=3 OBJECTIVE=285 P_FEAS=YES D_FEAS=YES INT_ITER=3 
      INT_FEAS=2 ACTIVE=0 INT_BEST=285 PHASE1_ITER=0 PHASE2_ITER=5 
      PHASE3_ITER=5
      

Preprocessing

Using the PREPROCESS= option, you can apply the preprocessing techniques to pre-solve and then solve the preceding mixed-integer program:

    proc lp preprocess=1 endpause;
    run;
    quit;
    %put &_orlp_;

The preprocessing statistics are written to the SAS log file as follows:

   NOTE: Preprocessing 1 ...
   NOTE:     2 upper bounds decreased.
   NOTE:     2 coefficients reduced.
   NOTE: Preprocessing 2 ...
   NOTE:     2 constraints eliminated.
   NOTE: Preprocessing done.

The new output _ORLP_ is as follows:


STATUS=SUCCESSFUL PHASE=3 OBJECTIVE=285 P_FEAS=YES D_FEAS=YES INT_ITER=0 
      INT_FEAS=1 ACTIVE=0 INT_BEST=285 PHASE1_ITER=0 PHASE2_ITER=5 
      PHASE3_ITER=0
      

In this example, the number of integer iterations (INT_ITER=) is zero, which means that the preprocessing has reduced the gap between the relaxed linear problem and the mixed-integer program to zero.