> > * 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.
This formula looks to be a standard one for computing the relative mip gap (it is used in many other packages, e.g. cplex, gurobi, etc.; see, for example, http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r4/index.jsp?topic=%2Filog.odms.cplex.help%2Frefcallablelibrary%2Fhtml%2Ffunctions%2FCPXgetmiprelgap.html ). By definition, the relative mip gap is the relative error relerr = |z - z*| / |z*| ~= |z - z*| / |z| between an approximation z (best_mip) and the exact optimum z*, which being unknown is replaced by its estimation (best_bnd). > > > 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. > Probably this formula is better in the sense of monotonicity, however, it would be more difficult to interprete corresponding values. _______________________________________________ Help-glpk mailing list [email protected] https://lists.gnu.org/mailman/listinfo/help-glpk
