If we had mathematical closed form formulas for bestfound and bestpossible we would not need a MIP solver. Epsilon is a small constant > 0 to prevent division by zero.
---------------------------------------------------------------- Erwin Kalvelagen Amsterdam Optimization Modeling Group [email protected] http://amsterdamoptimization.com ---------------------------------------------------------------- On Thu, Dec 3, 2015 at 12:35 PM, usa usa <[email protected]> wrote: > 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 < > [email protected]> 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 >> [email protected] >> http://amsterdamoptimization.com >> ---------------------------------------------------------------- >> >> On Thu, Dec 3, 2015 at 12:10 AM, usa usa <[email protected]> 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 >>> [email protected] >>> https://lists.gnu.org/mailman/listinfo/help-glpk >>> >>> >> >
_______________________________________________ Help-glpk mailing list [email protected] https://lists.gnu.org/mailman/listinfo/help-glpk
