Interpretation of GAP in CPLEX

Question

This is a part of the engine-log output that I get from a small-scale mixed integer linear optimization problem that I solved in CPLEX 12.7.0

    Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

      0     0      280.0338    78                    280.0338       72         
      0     0      428.8558    28                    Cuts: 89      137         
      0     0      429.5221    34                     Cuts: 2      142         
      0     0      429.7745    34                  MIRcuts: 2      143         
*     0+    0                          460.9166      429.7745             6.76%
      0     2      429.7745    34      460.9166      429.8666      143    6.74%
Elapsed time = 0.49 sec. (31.07 ticks, tree = 0.01 MB, solutions = 1)
*    35     8      integral     0      438.1448      435.6381      211    0.57%

Cover cuts applied:  17
Implied bound cuts applied:  10
Flow cuts applied:  11
Mixed integer rounding cuts applied:  9
Gomory fractional cuts applied:  24

Root node processing (before b&c):
  Real time             =    0.45 sec. (31.09 ticks)
Sequential b&c:
  Real time             =    0.08 sec. (20.80 ticks)
                          ------------
Total (root+branch&cut) =    0.53 sec. (51.89 ticks)

What I understand from this, is that the best integer solution (for the objective function) found has the value of 438.1448, whereas the relaxed solution (non integer values) has the value of 435.6381 as best bound solution.

( 438.1448 / 435.6381 ) - 1 = 0.57% GAP

Does this mean that the solution still has that small gap, however it is proven to be the optimal solution? I had the (maybe wrong) idea that optimality is proven by a 0% gap.

I'm not sure how to interpret it correctly. Thanks for your help in advance.

Yamamoto

Answer 1

Your understanding of the best bound isn't 100% correct. You can think of the best bound as the best objective value an integer solution could potentially have, based on information the solver has discovered so far. In your case there might actually be a better solution than the one you found, but if there is, it won't have an objective value better than 435.6381.

A more technical definition of the best bound is the best relaxed-but-region-constrained solution for any region that has not yet been eliminated from the search space. Solvers like CPLEX search for an optimal solution by splitting the search space into sub-regions and then ruling out sub-regions that can't possibly contain the optimal integer-feasible solution. These sub-regions get split into sub-sub-regions, and so on. Within each region, the original problem is modified to force variables to fall within the region. The relaxed solution to this modified problem is the best bound for the region. The best of these region-specific best bounds is the best bound for the problem as a whole.

The best bound changes as regions are ruled out. If the best bound does not equal the best solution, then by definition, there is still at least one region other than the region holding the current incumbent that could potentially hold a better solution. Exploring one of these regions might uncover an even better solution than your current incumbent, or it might lead to the region being ruled out. You don't know which until the region is explored. Only when the best solution equals the best bound do you know for sure that there isn't a better solution hiding in a remaining region.

Leatherleaf

Nice explanation – Reciprocal

Answer 2

Yes you are right. The optimality is proven if the upper bound and the lower bound evaluate the same value, i.e. CPLEX could prove an optimality gap of 0%.

Since CPLEX stops with a solution that has a gap of 0.57%, I would assume that you configured an MIP-gap <1%. If you are interested in a solution with proven optimal, you should change the MIPGap parameter to zero. See also here.

Bladderwort

Hi! Could you update the link in your answer, please? – Lamasery