help-glpk
[Top][All Lists]

## Re: [Help-glpk] Percentages...

 From: Andrew Makhorin Subject: Re: [Help-glpk] Percentages... Date: Wed, 20 Apr 2005 20:31:35 +0400

```>Can someone please explain generally how the percentages to optimality
>are calculated.  i.e. if I stop the solver at say 10% (for time
>efficiency) what does that mean with respect to the optimal solution.

The relative mip gap is computed as follows:

rel_gap = |best_mip - best_bound| / (|best_mip| + macheps),

where best_mip is the best integer feasible solution found so far,
best_bound is the best global bound. The exact optimum is always between
best_mip and best_bound whose values are output by glpk mip solver onto
the screen every 3 seconds or when one of these values has been changed.

Let, for example, best_mip = 123.456 and the problem is minimization.
Then rel_gap = 10% means that the exact optimum cannot be better (less)
than best_mip - 10% * best_mip = 123.456 - 12.3456 = 111.11 (note that
the latter quantity is the best global bound by definition).

```