How to determine different gap rates?

Question

I found in the literature different gaps:

• a gap between a random solution and an exact solution
• a gap between the exact solution and a lower bound
• a gap between the exact solution and a lower bound
• a gap between lower bound and upper bound

I am confused when writing the corresponding formula of each gap: what is the rule ( ?- ?)/(?) ?

Shall I use the gap between lower bound and upper bound only if I don't have an exact solution?

And what is the significance between these gaps and the gap returned by Cplex in terms of %?

Answer 1

MIP solvers such as CPLEX & Gurobi indicate a gap (in %) between the current best solution and the current best dual bound (which is a lower bound for a minimization problem). In general, the optimum value is not known until, well, the problem is solved.

Different solvers may use slightly different definitions:

• CPLEX: $$ g = \frac{|Z_{\rm dual} - Z_{\rm primal}|}{10^{-10} + |Z_{\rm primal}|}$$

• Gurobi $$ g = \frac{|Z_{\rm dual} - Z_{\rm primal}|}{|Z_{\rm primal}|}$$

• SCIP $$ g = \frac{|Z_{\rm dual} - Z_{\rm primal}|}{\min (|Z_{\rm dual}|, |Z_{\rm primal}|)} $$

In the case of CPLEX and Gurobi, you may interpret this as "the current solution cannot be improved by more than $g\%$". For a minimization problem, if the current best solution has objective value $150$ and the current gap is $2.3\%$, then there does not exist a feasible solution with objective value less than $150 - \frac{2.3}{100} \times 150 = 146.55$.

There are obviously some limitations to this formula:

• If the primal and lower bound have different signs
• If the primal value is $0$
• If no primal or dual bound is known (some solvers will report a gap of $+\infty$, some will report a gap of $100 \%$)

Answer 2

Gaps are typically tied to specific models and solution methods. The gap reflects the difference between the best known bound and the objective value of the best solution produced by a particular algorithm. How that is computed depends in part on whether you are minimizing and maximizing, in part on whether you want the gap as a fraction of the best solution or best bound, and in part on how you avoid dividing by zero. I believe expressing the gap as a fraction of the best bound is the more common approach, but I hesitate to say that it is universally adopted.

If $\hat{f}$ is the objective value of the incumbent (best known feasible solution) and $\bar{f}$ is the best known bound for the objective function, CPLEX computes the gap as $$\frac{|\hat{f}-\bar{f}|}{|\bar{f}| + 10^{-10}}$$ (and converts it to a percentage in the node log).

Regarding the difference between lower and upper bound, in a minimization problem the best known solution (whether known to be optimal or just the current incumbent) gives you the upper bound, and for a maximization the best known solution gives you the lower bound. So this is no different from the previous case.

If you have an exact solution, the value of that solution is also the best known bound, and so the difference between a "random solution" (incumbent) and the exact solution (best bound) is again covered by the above.

Answer 3

A short little note about computing gaps just appeared in 4OR:

Laporte, G., Toth, P. A gap in scientific reporting. 4OR-Q J Oper Res (2021). https://doi.org/10.1007/s10288-021-00483-0