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: 
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](https://www.ibm.com/support/knowledgecenter/en/SS9UKU_12.10.0/com.ibm.cplex.zos.help/CPLEX/Parameters/topics/EpGap.html):
$$ g = \frac{|Z\_{\rm dual} - Z\_{\rm primal}|}{10^{-10} + |Z\_{\rm primal}|}$$
* [Gurobi](https://www.gurobi.com/documentation/9.1/refman/mipgap.html)
$$ g = \frac{|Z\_{\rm dual} - Z\_{\rm primal}|}{|Z\_{\rm primal}|}$$
* [SCIP](https://www.scipopt.org/doc/html/PARAMETERS.php)
$$ 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 \%$)
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>