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 [email protected] "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 _______________________________________________ Help-glpk mailing list [email protected] https://lists.gnu.org/mailman/listinfo/help-glpk
