The OPTMILP Procedure

Example 11.2 MIPLIB Benchmark Instance

The following example illustrates the conversion of a standard MPS-format file into an MPS-format SAS data set. The problem is re-solved several times, each time by using a different control option. For such a small example, it is necessary to disable cuts and heuristics in order to see the computational savings gained by using other options. For larger or more complex examples, the benefits of using the various control options are more pronounced.

The standard set of MILP benchmark cases is called MIPLIB (Bixby et al. 1998, Achterberg, Koch, and Martin 2003) and can be found at http://miplib.zib.de/. The following statement uses the %MPS2SASD macro to convert an example from MIPLIB to a SAS data set:

                                                                                                       
%mps2sasd(mpsfile="bell3a.mps", outdata=mpsdata);  

The problem can then be solved using PROC OPTMILP on the data set created by the conversion:

                                                                                                  
proc optmilp data=mpsdata allcuts=none heuristics=none logfreq=10000;                                                                                                          
run;                                                                                                                                

The resulting log is shown in Output 11.2.1.

Output 11.2.1: MIPLIB PROC OPTMILP Log

 

NOTE: The problem BELL3A has 133 variables (39 binary, 32 integer, 0 free, 0    
      fixed).                                                                   
NOTE: The problem has 123 constraints (123 LE, 0 EQ, 0 GE, 0 range).            
NOTE: The problem has 347 constraint coefficients.                              
NOTE: The MILP presolver value AUTOMATIC is applied.                            
NOTE: The MILP presolver removed 33 variables and 37 constraints.               
NOTE: The MILP presolver removed 92 constraint coefficients.                    
NOTE: The MILP presolver modified 3 constraint coefficients.                    
NOTE: The presolved problem has 100 variables, 86 constraints, and 255          
      constraint coefficients.                                                  
NOTE: The MILP solver is called.                                                
          Node  Active    Sols    BestInteger      BestBound      Gap    Time   
             0       1       0              .         866240        .       0   
             0       1       0              .         866240        .       0   
           801      49       1         916564         874287    4.84%       0   
           881     108       2         916327         874287    4.81%       0   
           947     159       3         915158         874287    4.67%       0   
           979     165       4         898096         874287    2.72%       0   
          1002     123       5         887234         874287    1.48%       0   
          1088     122       6         883066         874287    1.00%       0   
          1978     381       7         880717         874502    0.71%       0   
          6093    1902       8         878430         875484    0.34%       0   
         10000    2382       8         878430         876000    0.28%       1   
         20000    1703       8         878430         876961    0.17%       2   
         23321       2       8         878430         878365    0.01%       2   
NOTE: Optimal within relative gap.                                              
NOTE: Objective = 878430.316.                                                   


Suppose you do not have a bound for the solution. If there is an objective value that, even if it is not optimal, satisfies your requirements, then you can save time by using the TARGET= option. The following PROC OPTMILP call solves the problem with a target value of 880,000:

                                                                                                                                                                    
proc optmilp data=mpsdata allcuts=none heuristics=none logfreq=5000 
             target=880000;                                                                                            
run;

The relevant results from this run are displayed in Output 11.2.2. In this case, there is a decrease in CPU time, but the objective value has increased.

Output 11.2.2: MIPLIB PROC OPTMILP Log with TARGET= Option

 

NOTE: The problem BELL3A has 133 variables (39 binary, 32 integer, 0 free, 0    
      fixed).                                                                   
NOTE: The problem has 123 constraints (123 LE, 0 EQ, 0 GE, 0 range).            
NOTE: The problem has 347 constraint coefficients.                              
NOTE: The MILP presolver value AUTOMATIC is applied.                            
NOTE: The MILP presolver removed 33 variables and 37 constraints.               
NOTE: The MILP presolver removed 92 constraint coefficients.                    
NOTE: The MILP presolver modified 3 constraint coefficients.                    
NOTE: The presolved problem has 100 variables, 86 constraints, and 255          
      constraint coefficients.                                                  
NOTE: The MILP solver is called.                                                
          Node  Active    Sols    BestInteger      BestBound      Gap    Time   
             0       1       0              .         866240        .       0   
             0       1       0              .         866240        .       0   
           801      49       1         916564         874287    4.84%       0   
           881     108       2         916327         874287    4.81%       0   
           947     159       3         915158         874287    4.67%       0   
           979     165       4         898096         874287    2.72%       0   
          1002     123       5         887234         874287    1.48%       0   
          1088     122       6         883066         874287    1.00%       0   
          1978     381       7         880717         874502    0.71%       0   
          5000    1476       7         880717         875311    0.62%       0   
          6093    2011       8         878430         875484    0.34%       0   
NOTE: Target reached.                                                           
NOTE: Objective of the best integer solution found = 878430.32.                 


When the objective value of a solution is within a certain relative gap of the optimal objective value, the procedure stops. The acceptable relative gap can be changed using the RELOBJGAP= option, as demonstrated in the following example:

                                                                                                                                                               
proc optmilp data=mpsdata allcuts=none heuristics=none relobjgap=0.01;                                                                                           
run;                                                                                                                                

The relevant results from this run are displayed in Output 11.2.3. In this case, since the specified RELOBJGAP= value is larger than the default value, the number of nodes and the CPU time have decreased from their values in the original run. Note that these savings are exchanged for an increase in the objective value of the solution.

Output 11.2.3: MIPLIB PROC OPTMILP Log with RELOBJGAP= Option

 

NOTE: The problem BELL3A has 133 variables (39 binary, 32 integer, 0 free, 0    
      fixed).                                                                   
NOTE: The problem has 123 constraints (123 LE, 0 EQ, 0 GE, 0 range).            
NOTE: The problem has 347 constraint coefficients.                              
NOTE: The MILP presolver value AUTOMATIC is applied.                            
NOTE: The MILP presolver removed 33 variables and 37 constraints.               
NOTE: The MILP presolver removed 92 constraint coefficients.                    
NOTE: The MILP presolver modified 3 constraint coefficients.                    
NOTE: The presolved problem has 100 variables, 86 constraints, and 255          
      constraint coefficients.                                                  
NOTE: The MILP solver is called.                                                
          Node  Active    Sols    BestInteger      BestBound      Gap    Time   
             0       1       0              .         866240        .       0   
             0       1       0              .         866240        .       0   
           100      85       0              .         873180        .       0   
           200     166       0              .         873577        .       0   
           300     243       0              .         873730        .       0   
           400     317       0              .         873867        .       0   
           500     379       0              .         874141        .       0   
           600     460       0              .         874247        .       0   
           700     544       0              .         874262        .       0   
           800      50       0              .         874287        .       0   
           801      49       1         916564         874287    4.84%       0   
           881     108       2         916327         874287    4.81%       0   
           900     125       2         916327         874287    4.81%       0   
           947     159       3         915158         874287    4.67%       0   
           979     165       4         898096         874287    2.72%       0   
          1000     185       4         898096         874287    2.72%       0   
          1002     123       5         887234         874287    1.48%       0   
          1088     122       6         883066         874287    1.00%       0   
          1100     129       6         883066         874287    1.00%       0   
          1200     168       6         883066         874287    1.00%       0   
          1300     199       6         883066         874287    1.00%       0   
          1400     238       6         883066         874287    1.00%       0   
          1500     266       6         883066         874287    1.00%       0   
          1600     302       6         883066         874287    1.00%       0   
          1700     327       6         883066         874314    1.00%       0   
          1736     341       6         883066         874325    1.00%       0   
NOTE: Optimal within relative gap.                                              
NOTE: Objective = 883066.108.                                                   


The MAXTIME= option enables you to accept the best solution produced by PROC OPTMILP in a specified amount of time. The following example illustrates the use of the MAXTIME= option:

                                                                                                                                                                       
proc optmilp data=mpsdata allcuts=none heuristics=none maxtime=0.1;                                                                                                
run;                                                                                                                                

The relevant results from this run are displayed in Output 11.2.4. Once again, a reduction in solution time is traded for an increase in objective value.

Output 11.2.4: MIPLIB PROC OPTMILP Log with MAXTIME= Option

 

NOTE: The problem BELL3A has 133 variables (39 binary, 32 integer, 0 free, 0    
      fixed).                                                                   
NOTE: The problem has 123 constraints (123 LE, 0 EQ, 0 GE, 0 range).            
NOTE: The problem has 347 constraint coefficients.                              
NOTE: The MILP presolver value AUTOMATIC is applied.                            
NOTE: The MILP presolver removed 33 variables and 37 constraints.               
NOTE: The MILP presolver removed 92 constraint coefficients.                    
NOTE: The MILP presolver modified 3 constraint coefficients.                    
NOTE: The presolved problem has 100 variables, 86 constraints, and 255          
      constraint coefficients.                                                  
NOTE: The MILP solver is called.                                                
          Node  Active    Sols    BestInteger      BestBound      Gap    Time   
             0       1       0              .         866240        .       0   
             0       1       0              .         866240        .       0   
           100      85       0              .         873180        .       0   
           200     166       0              .         873577        .       0   
           203     167       0              .         873577        .       0   
NOTE: CPU time limit reached.                                                   
NOTE: No integer solutions found.                                               


The MAXNODES= option enables you to limit the number of nodes generated by PROC OPTMILP. The following example illustrates the use of the MAXNODES= option:

                                                                                                      
proc optmilp data=mpsdata allcuts=none heuristics=none maxnodes=500;                                                                                  
run;                                                                                                                                

The relevant results from this run are displayed in Output 11.2.5. PROC OPTMILP displays the best objective value of all the solutions produced.

Output 11.2.5: MIPLIB PROC OPTMILP Log with MAXNODES= Option

 

NOTE: The problem BELL3A has 133 variables (39 binary, 32 integer, 0 free, 0    
      fixed).                                                                   
NOTE: The problem has 123 constraints (123 LE, 0 EQ, 0 GE, 0 range).            
NOTE: The problem has 347 constraint coefficients.                              
NOTE: The MILP presolver value AUTOMATIC is applied.                            
NOTE: The MILP presolver removed 33 variables and 37 constraints.               
NOTE: The MILP presolver removed 92 constraint coefficients.                    
NOTE: The MILP presolver modified 3 constraint coefficients.                    
NOTE: The presolved problem has 100 variables, 86 constraints, and 255          
      constraint coefficients.                                                  
NOTE: The MILP solver is called.                                                
          Node  Active    Sols    BestInteger      BestBound      Gap    Time   
             0       1       0              .         866240        .       0   
             0       1       0              .         866240        .       0   
           100      85       0              .         873180        .       0   
           200     166       0              .         873577        .       0   
           300     243       0              .         873730        .       0   
           400     317       0              .         873867        .       0   
           499     378       0              .         874141        .       0   
NOTE: Node limit reached.                                                       
NOTE: No integer solutions found.