Thanks, This is conceptial level formula.
I need a mathematical formula for "bestfound", "bestpossible" and "epsilon". For example, in GLPK, primal-dual simplex algorithm and branch-bound algorithm, whare are the gap formulas ? How to estimate the "bestpossible" and "epsilon" without solving an integer programming model ? How to estimate the "bestpossible" and "epsilon" without solving an linear programming model ? Any help would be appreciated. Thanks ! David On Thu, Dec 3, 2015 at 12:20 AM, Erwin Kalvelagen < erwin.kalvela...@gmail.com> wrote: > Different solvers use different definitions. Here are some examples of how > a definition of the relative gap can look like: > > abs(bestpossible - bestfound) / abs(bestpossible) > > abs(bestpossible - bestfound) / (abs(bestfound) + epsilon) > > > No matter what: 0% means optimal > > > ---------------------------------------------------------------- > Erwin Kalvelagen > Amsterdam Optimization Modeling Group > er...@amsterdamoptimization.com > http://amsterdamoptimization.com > ---------------------------------------------------------------- > > On Thu, Dec 3, 2015 at 12:10 AM, usa usa <usact2...@gmail.com> wrote: > >> Hi, >> >> I would like to find the theoretic formula about the integrality gap for >> >> 1. Mixed integer linear programing model and its linear programming >> relaxation >> 2. 0-1 knapsack integer programing model and its linear programming >> relaxation >> >> Sometimes the gao may be called relative error or approximation ratio. >> >> I would like to see the formula that express the gap mathematically. >> >> Any help would be appreciated. >> >> Best Regards, >> >> David >> >> _______________________________________________ >> Help-glpk mailing list >> Help-glpk@gnu.org >> https://lists.gnu.org/mailman/listinfo/help-glpk >> >> >
_______________________________________________ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
