[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## Re: [Help-glpk] info

**From**: |
Andrew Makhorin |

**Subject**: |
Re: [Help-glpk] info |

**Date**: |
Wed, 01 Aug 2012 15:10:47 +0400 |

>* > * The routine ios_relative_gap computes the relative mip gap using the*
>* > * formula:*
>* > **
>* > * gap = |best_mip - best_bnd| / (|best_mip| + DBL_EPSILON)*
>* *
>* > Beware: The mip gap may rise while you solution gets better:*
>* *
>* Ouch. Not a good formula.*
This formula looks to be a standard one for computing the relative mip
gap (it is used in many other packages, e.g. cplex, gurobi, etc.; see,
for example,
http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r4/index.jsp?topic=%2Filog.odms.cplex.help%2Frefcallablelibrary%2Fhtml%2Ffunctions%2FCPXgetmiprelgap.html
). By definition, the relative mip gap is the relative error
relerr = |z - z*| / |z*| ~= |z - z*| / |z|
between an approximation z (best_mip) and the exact optimum z*, which
being unknown is replaced by its estimation (best_bnd).
>* *
>* > Integer optimization begins...*
>* > + 213: mip = not found yet <= +inf (1; 0)*
>* > + 481: >>>>> -4.000000000e+00 <= 7.000000000e+00 275.0% (10; 0)*
>* > + 875: >>>>> -3.000000000e+00 <= 2.600000000e+00 186.7% (15; 3)*
>* > + 1215: >>>>> -1.000000000e+00 <= 1.000000000e+00 200.0% (15; 11)*
>* > + 1397: mip = -1.000000000e+00 <= tree is empty 0.0% (0; 47)*
>* > INTEGER OPTIMAL SOLUTION FOUND*
>* >*
>* > The mip gap rose from 1.867 to 2. while the objective rose from -3 to -1*
>* > in this maximization problem.*
>* *
>* Perhaps this formula would be better:*
>* |best_mip - best_bnd|/|best_mip - root_bnd|,*
>* where root_bnd is the bound found at the root.*
>* It produces 0/0 if the root solution is feasible,*
>* but otherwise is non-increasing once one has a solution.*
>* *
Probably this formula is better in the sense of monotonicity, however,
it would be more difficult to interprete corresponding values.

**Re: [Help-glpk] info**,
*Andrew Makhorin* **<=**