Re: [Help-glpk] info

[Michael Hennebry]

On Wed, 1 Aug 2012, Andrew Makhorin wrote:

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

Not disputing it's standardness, merely its utility:

> > > Beware: The mip gap may rise while you solution gets better:

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

What do you want to happen if z is near zero?

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

It is also invariant under linear transforms.

--
Michael   address@hidden
"On Monday, I'm gonna have to tell my kindergarten class,
whom I teach not to run with scissors,
that my fiance ran me through with a broadsword."  --  Lily