I understood this. I would like to find how to matehmatically formulate the gap as accurate as possible.
Although the gap may not be very accurate, it is better that it can give us a confidence to trust the approximate solution. Thanks ! On Thu, Dec 3, 2015 at 1:35 PM, Erwin Kalvelagen < [email protected]> wrote: > 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
