help-glpk
[Top][All Lists]

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

 From: Michael Hennebry Subject: Re: [Help-glpk] typo in mip gap formula on wikibook page Date: Fri, 3 May 2013 11:00:51 -0500 (CDT) User-agent: Alpine 1.00 (DEB 882 2007-12-20)

```On Thu, 2 May 2013, Andrew Makhorin wrote:

```
```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.
```
```
http://en.wikipedia.org/wiki/Approximation_error:
```
```There are two features of relative error that should be kept in mind.
Firstly, relative error is undefined when the true value is zero as
it appears in the denominator (see below).
Secondly, relative error only makes sense when measured on a ratio scale,
(i.e. a scale which has a true meaningful zero), otherwise it would be
sensitive to the measurement units. For example, when an absolute error
in a temperature measurement given in Celsius is 1° and the true value
is 2°C, the relative error is 0.5 and the percent error is 50%.
For this same case, when the temperature is given in Kelvin,
the same 1° absolute error with the same true value of 275.15° K gives
a relative error of 3.63e-3 and a percent error of only 0.363%.
Celsius temperature is measured on an interval scale,
whereas the Kelvin scale has a true zero and so is a ratio scale.
```
```
My suggestion has the effect of inducing a true zero.
BTW I didn't make it up.
I first encountered it in early literature on TSPs.

On Thu, 2 May 2013, Andrew Makhorin wrote:
```
```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.
```
```
Why print the mip gap at all?
The answer to that question should tell you whether to print it.

Also using the current mip gap in a stopping
criterion is not necessarily a good idea.
If one has enough knowledge to use it, one might as well use absolute error.
Temperatures near room temperature are an example.

--