Re: [Help-glpk] typo in mip gap formula on wikibook page

[Andrew Makhorin]

On Mon, 2013-04-29 at 18:48 -0500, Michael Hennebry wrote:
> On Sat, 27 Apr 2013, Heinrich Schuchardt wrote:
> 
> > the current definition of the MIP gap is compatible to other optimizers
> > like CPLEX.
> 
> To the best of of my knowledge,
> the terminal output is designed to be read by humans.
> It will not be inerpreted by another program.
> There is no compatibility issue.
> 
> > The advantage of the current definition has the advantage of beeing
> > meaningful to the
> > end user.
> >  
> > If the gap is 1 % and the current MIP solution costs me 1 Mio Euro, I
> > know that even
> > if there is a better solution, it cannot be better by more than 9901
> > Euro. Your proposed
> > definition would not have such economic significance.
> 
> You would not need the 1%.
> An optimistic bound is one of the numbers provided on the same line.
> 
> On the other hand, were the objective temperature,
> the relative gap would change depending on whether
> it was expressed in Fahrenheit or Celcius.
> 
> My denominator would provide a better indication
> of how hard it would be to close the gap.
> 
> That said, Andrew has already expressed an unwillingness to change it.
> 
> Heinrich Schuchardt quoted Michael Hennebry:
> > I'd suggest that a better denominator would be |best_mip - root_lp| That
> > would make the formula immune to shifts and scalings. It would also
> > ensure that the gap was never greater than 100% .

The mip gap has the same meaning as the relative error (please see
http://en.wikipedia.org/wiki/Approximation_error ), so changing the
formula would confuse the user. A requirement to make the result
"immune ... and never greater than 100%" looks too artificial.

Probably, in order to avoid a meaningless result when the lower and
upper objective bounds have different signs, the mip gap should not be
computed at all.

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