[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Andrew Makhorin
Subject: Re: [Help-glpk] typo in mip gap formula on wikibook page
Date: Thu, 02 May 2013 15:09:11 +0400

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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]