It may come as a surprise, but the MIP gap can increase. From a Cplex log:
Nodes Cuts/ Node Left Objective IInf Best Integer Best Bound ItCnt Gap * 0+ 0 300.0000 -120.0000 140.00% Found incumbent of value 300.000000 after 0.09 sec. (5.80 ticks) 0 0 -120.0000 153 300.0000 -120.0000 229 140.00% 0 0 -120.0000 163 300.0000 Cuts: 118 356 140.00% 0 0 -120.0000 129 300.0000 Cuts: 64 427 140.00% 0 0 -120.0000 142 300.0000 Cuts: 180 503 140.00% * 0+ 0 -10.0000 -120.0000 --- Found incumbent of value -10.000000 after 0.31 sec. (67.99 ticks) 0 2 -120.0000 128 -10.0000 -120.0000 503 --- Elapsed time = 0.33 sec. (71.72 ticks, tree = 0.01 MB, solutions = 2) 414 350 -120.0000 155 -10.0000 -120.0000 8074 --- Cuts: 60 * 500+ 375 -30.0000 -120.0000 300.00% Cuts: 4 Found incumbent of value -30.000000 after 1.44 sec. (418.43 ticks) 500 377 -110.0000 148 -30.0000 -120.0000 9855 300.00% 610 483 -120.0000 157 -30.0000 -120.0000 12092 300.00% 632 376 -120.0000 176 -30.0000 -120.0000 12662 300.00% 710 268 -110.0000 166 -30.0000 -120.0000 13622 300.00% 950 360 -73.0094 112 -30.0000 -120.0000 16832 300.00% Cuts: 216 1110 430 -89.6733 148 -30.0000 -120.0000 19495 300.00% 1398 650 -91.0030 118 -30.0000 -120.0000 25098 300.00% Cuts: 72 1759 958 -43.2768 95 -30.0000 -120.0000 31198 300.00% 3031 2036 -60.1740 97 -30.0000 -119.2262 49706 297.42% Elapsed time = 13.67 sec. (4413.94 ticks, tree = 0.73 MB, solutions = 3) 4721 3471 -77.9342 132 -30.0000 -116.6542 71843 288.85% Cuts: 42 5867 4399 -82.3794 152 -30.0000 -115.2913 89434 284.30% Cuts: 8 7276 5520 -95.5742 137 -30.0000 -113.0523 107572 276.84% Cuts: 20 8729 6670 -68.9411 119 -30.0000 -110.8877 127085 269.63% Cuts: 28 9919 7614 -40.0000 86 -30.0000 -110.0000 145286 266.67%
The reason is the Best Integer bound assumes vary small values when passing the x-axis.
GAP definitions
The Cplex definition of the relative gap is [1]:
\[\mathit{RelGap} = \frac{|\mathit{BestBound}-\mathit{BestInteger}|}{10^{-10}+ |\mathit{BestInteger}|} \]
This means the following scenario is possible:
This means the following scenario is possible:
Although he absolute gap (the difference between the grey and the orange line) is decreasing monotonically, the relative gap (the yellow line) is not. Note that the gap relates to the scale on the right (with percentages). Just to be sure: the horizontal axis is time.
Often the BestBound and the BestInteger quantities are called the Lower and Upper Bound. (Note: this makes sense when minimizing. If maximizing we need to flip these.) So we can write the Cplex relative gap as (approximately):
\[ \mathit{RelGap} = \frac{|U-L|}{ |U|} \]
Most solvers use a similar relative gap. Some solvers such as Baron [2] use a slightly different definition:
\[ \mathit{RelGap} = \frac{|U-L|}{ |L|} \]
In this case the Baron relative gaps are better than the ones for Cplex. This is not always the case. Below is a Baron log:
Often the BestBound and the BestInteger quantities are called the Lower and Upper Bound. (Note: this makes sense when minimizing. If maximizing we need to flip these.) So we can write the Cplex relative gap as (approximately):
\[ \mathit{RelGap} = \frac{|U-L|}{ |U|} \]
\[ \mathit{RelGap} = \frac{|U-L|}{ |L|} \]
This can make a difference. When using bounds in the picture, the Baron relative gap would look like:
Iteration Open nodes Time (s) Lower bound Upper bound * 1 1 4.00 0.00000 10.0000 1 1 4.00 0.376100E-01 10.0000 12+ 6 34.00 2.50000 10.0000 19+ 11 65.00 2.55875 10.0000 29+ 14 95.00 2.55875 10.0000 40+ 18 125.00 2.55875 10.0000 51+ 19 156.00 2.56067 10.0000 59+ 17 186.00 2.73249 10.0000 70+ 17 217.00 3.32720 10.0000 81+ 14 247.00 4.10826 10.0000 88+ 14 277.00 5.00000 10.0000 100+ 10 308.00 5.15290 10.0000 111+ 6 338.00 5.51454 10.0000 123+ 4 368.00 5.98316 10.0000 129 0 382.00 9.09091 10.0000
If we calculate both relative gaps for these bounds we see:
Here the Baron gap is more difficult.
GAMS suggests an even more crazy formula [3]:
\[ \mathit{RelGap} = \frac{|U-L|}{\max( |U|,|L|)} \]
Finally returning to our first Cplex log. We see very large gaps. If you are embarrassed about these large gaps, you can easily reformulate the objective. After using \[\min\> z = 1000 + z_{\text{orig}}\] we see:
Nodes Cuts/ Node Left Objective IInf Best Integer Best Bound ItCnt Gap * 0+ 0 1300.0000 880.0000 32.31% Found incumbent of value 1300.000000 after 0.08 sec. (5.85 ticks) 0 0 880.0000 153 1300.0000 880.0000 229 32.31% 0 0 880.0000 163 1300.0000 Cuts: 118 356 32.31% 0 0 880.0000 129 1300.0000 Cuts: 64 427 32.31% 0 0 880.0000 142 1300.0000 Cuts: 180 503 32.31% * 0+ 0 990.0000 880.0000 11.11% Found incumbent of value 990.000000 after 0.41 sec. (68.34 ticks) 0 2 880.0000 128 990.0000 880.0000 503 11.11% Elapsed time = 0.80 sec. (72.31 ticks, tree = 0.01 MB, solutions = 2) 2579 2059 923.8533 99 990.0000 880.0000 31891 11.11% Cuts: 78 * 2581+ 1437 980.0000 880.0000 10.20% Found incumbent of value 980.000000 after 2.05 sec. (311.11 ticks)
So just looking at the relative gap in isolation is not that useful: we can always fudge it.
References
- Cplex Relative MIP gap tolerance, https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.cplex.help/CPLEX/Parameters/topics/EpGap.html
- Baron Manual, http://www.minlp.com/downloads/docs/baron%20manual.pdf
- What is optca/optcr? https://support.gams.com/solver:what_is_optca_optcr
No comments:
Post a Comment