Branch-and-bound algorithms (as they are used for MIP and sometimes for (MI)QCP and (MI)NLP) maintain two very important numbers: “best estimate” and “best integer”. The “best integer” is the best solution that satisfies all integer requirements found so far. The “best estimate” provides a bound for the optimal integer solution.
For example, you have a maximization problem and the algorithms found an integer solution with objective value 10 (hence “best integer = 10). Moreover the algorithm communicates through the “best estimate”, which is e.g. 15, that the upper bound for the optimal solution of this problem is 15.
Having those two numbers we can calculate the “quality” of the best integer. The quality of a solution can be measured as the distance from the optimal solution. Unfortunately, we don't have the optimal solution, but we have a bound for the optimal solution (“best estimate”). Hence an upper bound for the distance between best integer and optimal solution is “best estimate” - “best integer”. This value is called the absolute gap (GAMS notation OPTCA). By providing the option OPTCA in a GAMS program you allow the solver to stop if the absolute gap drops below OPTCA. In our small example: The absolute gap is 5 = (15 - 10). If OPTCA >= 5 we would stop. The GAMS default for OPTCA is 0.
The absolute gap depends on the magnitude of the numbers “best estimate” and “best integer”. For example, if “best integer” = 10000 and “best estimate” = 15000 the absolute gap is 5000. In relative terms the quality of that solution is similar that the solution pair 10/15. For that reason there is the “relative gap” (in GAMS notation OPTCR) which is (“best estimate”-“best integer)/max(abs(“best estimate”), abs(“best integer”)) (and 1.0 if the sign of best estimate and best integer differ). Hence the “relative gap” for both example would be 0.33, i.e. 33% (100*OPTCR) from the best estimate. If the relative gap drops below OPTCR the algorithm terminates. The GAMS default for OPTCR is 0.1.
Note, for a general gap calculation you have to be careful about the signs of your number and the direction of optimization (min/max). Some of our solver (e.g. CPLEX) divide by the “best integer” to derive the relative gap.
The relative and absolute gap are not directly available as model attributes, but one can compute either of them quite easily. For example, we compute the relative and absolute gap of the model
rotdk from the GAMS model library. Please note that Cplex uses a slightly different definition for optcr of than GAMS normally uses.
$call gamslib rotdk $offlisting option solprint=off, mip=cplex; $include rotdk.gms $onlisting scalars optca absolute gap optcr relative gap following the GAMS formula optcr_cp relative gap following the Cplex formula delta gams cplex difference; optca = abs(rotdk.objest - rotdk.objval); optcr = optca / max(abs(rotdk.objest),abs(rotdk.objval)); optcr_cp = optca /(1e-10+abs(rotdk.objval)); delta = optcr - optcr_cp; option decimals=6; display optcr, optcr_cp, optca,delta ;
---- 87 PARAMETER optcr = 0.016860 relative gap following the GAMS formula PARAMETER optcr_cp = 0.016860 relative gap following the Cplex formula PARAMETER optca = 33.001572 absolute gap PARAMETER delta = 8.63892E-16 gams cplex difference