User Tools

Site Tools



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

Link to this comparison view

Both sides previous revision Previous revision
solver:what_is_optca_optcr [2020/09/30 19:35]
Atharv Bhosekar removed
— (current)
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 
-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 
-option solprint=off,​ mip=cplex; 
-$include rotdk.gms 
-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