Monday, March 26, 2018

MIP Gap Artifacts

For large integer programming models we may not be always willing to wait for a global, proven optimal solution. A straightforward way to deal with this is to set a time limit. A different way is to set a gap tolerance on the gap between the best possible and the best found integer solution. A typical gap tolerance is a few percent. Integer solvers display the gap prominently in the log. In most cases we talk about a relative gap. There is also an absolute gap with a corresponding absolute gap tolerance. In the following I talk about the relative gap.

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:

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|}$

This can make a difference. When using bounds in the picture, the Baron relative gap would look like:

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:

  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

1. Cplex Relative MIP gap tolerance, https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.cplex.help/CPLEX/Parameters/topics/EpGap.html