# GAMS Support Wiki

### Site Tools

solver:what_is_optca_optcr

# Differences

This shows you the differences between two versions of the page.

 solver:what_is_optca_optcr [2020/09/30 19:35]Atharv Bhosekar removed — (current) Both sides previous revision Previous revision 2020/09/30 19:35 Atharv Bhosekar removed2015/12/15 10:48 tlastusilta 2014/06/13 23:46 support 2013/09/10 10:32 support branch and bound is not limited to mip2007/09/18 15:59 external edit 2020/09/30 19:35 Atharv Bhosekar removed2015/12/15 10:48 tlastusilta 2014/06/13 23:46 support 2013/09/10 10:32 support branch and bound is not limited to mip2007/09/18 15:59 external edit Line 1: Line 1: - ====== What is optca/​optcr?​ ====== - - 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. - <​code>​ - \$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 ;​ - <​code>​ - ----     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 -