Previous Page | Next Page

The OPTMILP Procedure

Example 18.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 A. Martin 2003) and can be found at http://miplib.zib.de/. The following code uses the %MPS2SASD macro to convert an example from MIPLIB to a SAS data set:

                                                                                                       
%mps2sasd(mpsfile="p0282.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;                                                                                                          
run;                                                                                                                                

The resulting log is shown in Output 18.2.1.

Output 18.2.1 MIPLIB PROC OPTMILP Log
 

                                                                                 
NOTE: The problem P0282 has 282 variables (282 binary, 0 integer, 0 free, 0      
      fixed).                                                                    
NOTE: The problem has 241 constraints (241 LE, 0 EQ, 0 GE, 0 range).             
NOTE: The problem has 1966 constraint coefficients.                              
NOTE: The OPTMILP presolver value AUTOMATIC is applied.                          
NOTE: The OPTMILP presolver removed 80 variables and 80 constraints.             
NOTE: The OPTMILP presolver removed 682 constraint coefficients.                 
NOTE: The OPTMILP presolver modified 46 constraint coefficients.                 
NOTE: The presolved problem has 202 variables, 161 constraints, and 1284         
      constraint coefficients.                                                   
NOTE: The MIXED INTEGER LINEAR solver is called.                                 
          Node  Active    Sols    BestInteger      BestBound      Gap    Time    
             0       1       0              .         180000        .       0    
            45      45       1         258993         180000   43.88%       0    
           100      63       1         258993         255081    1.53%       0    
           139      91       2         258723         255193    1.38%       0    
           200     123       2         258723         255610    1.22%       0    
           300     135       2         258723         256316    0.94%       0    
           364     128       3         258411         256568    0.72%       0    
           400     118       3         258411         256732    0.65%       0    
           500     120       3         258411         257280    0.44%       0    
           600      54       3         258411         257878    0.21%       0    
           659       1       3         258411         258407    0.00%       0    
NOTE: Optimal within relative gap.                                               
NOTE: Objective = 258411.                                                        
                                                                                 
                                                                                 


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 260,000:

                                                                                                      
proc optmilp data=mpsdata allcuts=none heuristics=none target=260000;                                                                                            
run;                                                                                                                                

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

Output 18.2.2 MIPLIB PROC OPTMILP Log with TARGET= Option
 

                                                                                 
NOTE: The problem P0282 has 282 variables (282 binary, 0 integer, 0 free, 0      
      fixed).                                                                    
NOTE: The problem has 241 constraints (241 LE, 0 EQ, 0 GE, 0 range).             
NOTE: The problem has 1966 constraint coefficients.                              
NOTE: The OPTMILP presolver value AUTOMATIC is applied.                          
NOTE: The OPTMILP presolver removed 80 variables and 80 constraints.             
NOTE: The OPTMILP presolver removed 682 constraint coefficients.                 
NOTE: The OPTMILP presolver modified 46 constraint coefficients.                 
NOTE: The presolved problem has 202 variables, 161 constraints, and 1284         
      constraint coefficients.                                                   
NOTE: The MIXED INTEGER LINEAR solver is called.                                 
          Node  Active    Sols    BestInteger      BestBound      Gap    Time    
             0       1       0              .         180000        .       0    
            45      46       1         258993         180000   43.88%       0    
NOTE: Target reached.                                                            
NOTE: Objective of the best integer solution found = 258993.                     
                                                                                 
                                                                                 

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.10;                                                                                           
run;                                                                                                                                

The relevant results from this run are displayed in Output 18.2.3. In this case, since the specified RELOBJGAP= value is larger than the default value, the number of nodes as well as 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 18.2.3 MIPLIB PROC OPTMILP Log with RELOBJGAP= Option
 

                                                                                 
NOTE: The problem P0282 has 282 variables (282 binary, 0 integer, 0 free, 0      
      fixed).                                                                    
NOTE: The problem has 241 constraints (241 LE, 0 EQ, 0 GE, 0 range).             
NOTE: The problem has 1966 constraint coefficients.                              
NOTE: The OPTMILP presolver value AUTOMATIC is applied.                          
NOTE: The OPTMILP presolver removed 80 variables and 80 constraints.             
NOTE: The OPTMILP presolver removed 682 constraint coefficients.                 
NOTE: The OPTMILP presolver modified 46 constraint coefficients.                 
NOTE: The presolved problem has 202 variables, 161 constraints, and 1284         
      constraint coefficients.                                                   
NOTE: The MIXED INTEGER LINEAR solver is called.                                 
          Node  Active    Sols    BestInteger      BestBound      Gap    Time    
             0       1       0              .         180000        .       0    
            45      45       1         258993         180000   43.88%       0    
            56      42       1         258993         241020    7.46%       0    
NOTE: Optimal within relative gap.                                               
NOTE: Objective = 258993.                                                        
                                                                                 
                                                                                 

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 18.2.4. Once again, a reduction in solution time is traded for an increase in objective value.

Output 18.2.4 MIPLIB PROC OPTMILP Log with MAXTIME= Option
 

                                                                                 
NOTE: The problem P0282 has 282 variables (282 binary, 0 integer, 0 free, 0      
      fixed).                                                                    
NOTE: The problem has 241 constraints (241 LE, 0 EQ, 0 GE, 0 range).             
NOTE: The problem has 1966 constraint coefficients.                              
NOTE: The OPTMILP presolver value AUTOMATIC is applied.                          
NOTE: The OPTMILP presolver removed 80 variables and 80 constraints.             
NOTE: The OPTMILP presolver removed 682 constraint coefficients.                 
NOTE: The OPTMILP presolver modified 46 constraint coefficients.                 
NOTE: The presolved problem has 202 variables, 161 constraints, and 1284         
      constraint coefficients.                                                   
NOTE: The MIXED INTEGER LINEAR solver is called.                                 
          Node  Active    Sols    BestInteger      BestBound      Gap    Time    
             0       1       0              .         180000        .       0    
            45      45       1         258993         180000   43.88%       0    
           100      63       1         258993         255081    1.53%       0    
           139      91       2         258723         255193    1.38%       0    
           200     123       2         258723         255610    1.22%       0    
           300     135       2         258723         256316    0.94%       0    
           364     128       3         258411         256568    0.72%       0    
           400     118       3         258411         256732    0.65%       0    
           449     118       3         258411         257031    0.54%       0    
NOTE: CPU time limit reached.                                                    
NOTE: Objective of the best integer solution found = 258411.                     
                                                                                 
                                                                                 

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 18.2.5. PROC OPTMILP displays the best objective value of all the solutions produced.

Output 18.2.5 MIPLIB PROC OPTMILP Log with MAXNODES= Option
 

                                                                                 
NOTE: The problem P0282 has 282 variables (282 binary, 0 integer, 0 free, 0      
      fixed).                                                                    
NOTE: The problem has 241 constraints (241 LE, 0 EQ, 0 GE, 0 range).             
NOTE: The problem has 1966 constraint coefficients.                              
NOTE: The OPTMILP presolver value AUTOMATIC is applied.                          
NOTE: The OPTMILP presolver removed 80 variables and 80 constraints.             
NOTE: The OPTMILP presolver removed 682 constraint coefficients.                 
NOTE: The OPTMILP presolver modified 46 constraint coefficients.                 
NOTE: The presolved problem has 202 variables, 161 constraints, and 1284         
      constraint coefficients.                                                   
NOTE: The MIXED INTEGER LINEAR solver is called.                                 
          Node  Active    Sols    BestInteger      BestBound      Gap    Time    
             0       1       0              .         180000        .       0    
            45      45       1         258993         180000   43.88%       0    
           100      63       1         258993         255081    1.53%       0    
           139      91       2         258723         255193    1.38%       0    
           200     123       2         258723         255610    1.22%       0    
           300     135       2         258723         256316    0.94%       0    
           364     128       3         258411         256568    0.72%       0    
           400     118       3         258411         256732    0.65%       0    
           500     121       3         258411         257280    0.44%       0    
NOTE: Node limit reached.                                                        
NOTE: Objective of the best integer solution found = 258411.                     
                                                                                 
                                                                                 

Previous Page | Next Page | Top of Page