help-glpk
[Top][All Lists]

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

```