Example 16.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 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 16.2.1.
Output 16.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 43 1 258993 180000 43.88% 0 |
| 100 63 1 258993 254952 1.59% 0 |
| 150 84 2 258723 255333 1.33% 0 |
| 200 105 2 258723 255541 1.25% 0 |
| 300 147 2 258723 255840 1.13% 0 |
| 400 141 2 258723 256499 0.87% 0 |
| 500 114 2 258723 257311 0.55% 0 |
| 581 46 3 258411 258083 0.13% 0 |
| 600 29 3 258411 258217 0.08% 0 |
| 623 8 3 258411 258387 0.01% 0 |
| NOTE: Optimal within relative gap. |
| NOTE: Objective = 258411. |
| NOTE: PROCEDURE OPTMILP used (Total process time): |
| real time 0.15 seconds |
| cpu time 0.15 seconds |
| |
| |
| |
|
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 16.2.2. In this case,
there is a decrease in CPU time, but the objective value has increased.
Output 16.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 44 1 258993 180000 43.88% 0 |
| NOTE: Target reached. |
| NOTE: Objective of the best integer solution found = 258993. |
| NOTE: PROCEDURE OPTMILP used (Total process time): |
| real time 0.04 seconds |
| cpu time 0.04 seconds |
| |
| |
| |
|
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 16.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 16.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 43 1 258993 180000 43.88% 0 |
| 56 42 1 258993 241020 7.46% 0 |
| NOTE: Optimal within relative gap. |
| NOTE: Objective = 258993. |
| NOTE: PROCEDURE OPTMILP used (Total process time): |
| real time 0.06 seconds |
| cpu time 0.06 seconds |
| |
| |
| |
|
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 16.2.4. Once again, a
reduction in solution time is traded for an increase in objective value.
Output 16.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 43 1 258993 180000 43.88% 0 |
| 100 63 1 258993 254952 1.59% 0 |
| 150 84 2 258723 255333 1.33% 0 |
| 200 105 2 258723 255541 1.25% 0 |
| 300 147 2 258723 255840 1.13% 0 |
| NOTE: CPU time limit reached. |
| NOTE: Objective of the best integer solution found = 258723. |
| NOTE: PROCEDURE OPTMILP used (Total process time): |
| real time 0.10 seconds |
| cpu time 0.10 seconds |
| |
| |
| |
|
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 16.2.5. PROC OPTMILP
displays the best objective value of all the solutions produced.
Output 16.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 43 1 258993 180000 43.88% 0 |
| 100 63 1 258993 254952 1.59% 0 |
| 150 84 2 258723 255333 1.33% 0 |
| 200 105 2 258723 255541 1.25% 0 |
| 300 147 2 258723 255840 1.13% 0 |
| 400 141 2 258723 256499 0.87% 0 |
| 500 115 2 258723 257310 0.55% 0 |
| NOTE: Node limit reached. |
| NOTE: Objective of the best integer solution found = 258723. |
| NOTE: PROCEDURE OPTMILP used (Total process time): |
| real time 0.14 seconds |
| cpu time 0.14 seconds |
| |
| |
| |
|
