The LP Procedure

An Integer Programming Example

The following is a simple mixed-integer programming problem. Details can be found in Example 3.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
 

Figure 3.1: The Output of _ORLP_

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
 

Figure 3.2: The Output of _ORLP_ with Preprocessing Option On

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.