[Top][All Lists]

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

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

reply via email to

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