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
Next revision
Previous revision
solver:what_is_optca_optcr [2015/12/15 10:48]
— (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 
IMPRESSUM / LEGAL NOTICEPRIVACY POLICY solver/what_is_optca_optcr.1450172933.txt.gz ยท Last modified: 2015/12/15 10:48 by tlastusilta