Re: [Help-glpk] info

[Andrew Makhorin]

> > *  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.