[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
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
- Re: [Help-glpk] typo in mip gap formula on wikibook page,
Andrew Makhorin <=