Re: [Help-glpk] info

[Michael Hennebry]

On Mon, 30 Jul 2012, Xypron wrote:

> *  The routine ios_relative_gap computes the relative mip gap using the
> *  formula:
> *
> *     gap = |best_mip - best_bnd| / (|best_mip| + DBL_EPSILON)

> Beware: The mip gap may rise while you solution gets better:

Ouch.  Not a good formula.

> Integer optimization begins...
> +   213: mip =     not found yet <=              +inf        (1; 0)
> +   481: >>>>>  -4.000000000e+00 <=   7.000000000e+00 275.0% (10; 0)
> +   875: >>>>>  -3.000000000e+00 <=   2.600000000e+00 186.7% (15; 3)
> +  1215: >>>>>  -1.000000000e+00 <=   1.000000000e+00 200.0% (15; 11)
> +  1397: mip =  -1.000000000e+00 <=     tree is empty   0.0% (0; 47)
> INTEGER OPTIMAL SOLUTION FOUND
>
> The mip gap rose from 1.867 to 2. while the objective rose from -3 to -1
> in this maximization problem.

Perhaps this formula would be better:
|best_mip - best_bnd|/|best_mip - root_bnd|,
where root_bnd is the bound found at the root.
It produces 0/0 if the root solution is feasible,
but otherwise is non-increasing once one has a solution.

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