Re: [Help-glpk] the theoretic formula about the integrality gap for MILP and 0-1 knapsack integer programing model
GLPK uses |best_found - best_bound|/(|best_found| + DBL_EPSILON) . A better formula would be to get rid of the absolute values and replace DBL_EPSILON with -lp_obj, the negative of the LP relaxation's objective value. The man that matters disagrees and is more interested in copying CLPEX. My suggestion can result in 0/0 iff the MIP has the same objective value as its LP relaxation. At that point, the MIP has been solved. -- Michael henne...@web.cs.ndsu.nodak.edu "Sorry but your password must contain an uppercase letter, a number, a haiku, a gang sign, a heiroglyph, and the blood of a virgin." -- someeecards ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] the theoretic formula about the integrality gap for MILP and 0-1 knapsack integer programing model
Hi, Andrews, For one numerical instance, your method works. What I need is the mathematical formula for the gap. Example, given IP : max. C x W s.t A x W <= B x is 0, 1 integer What is gap between the IP and its Linear programming relaxation ? the gap can only be expressed by A, B, C and other constants if necessary. Also, what is "any (*not LP*) relaxation of MIP" in your reply ? What does the "*LP*" mean here ? Thanks On Thu, Dec 3, 2015 at 2:52 PM, Andrew Makhorin wrote: > > > > How to estimate the "bestpossible" and "epsilon" > > without solving an integer programming model ? > > Find any integer feasible solution to MIP (not solving MIP exactly), > e.g. with a primal heuristic--it gives you "bestfound". > > > > > > > How to estimate the "bestpossible" and "epsilon" > > without solving an linear programming model ? > > Find an optimal solution to any (not LP) relaxation of MIP--it gives you > "bestpossible". > > Take "epsilon" as a smallest floating-point number such that 1+eps > 1. > > > ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] the theoretic formula about the integrality gap for MILP and 0-1 knapsack integer programing model
> How to estimate the "bestpossible" and "epsilon" > without solving an integer programming model ? Find any integer feasible solution to MIP (not solving MIP exactly), e.g. with a primal heuristic--it gives you "bestfound". > > > How to estimate the "bestpossible" and "epsilon" > without solving an linear programming model ? Find an optimal solution to any (not LP) relaxation of MIP--it gives you "bestpossible". Take "epsilon" as a smallest floating-point number such that 1+eps > 1. ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] the theoretic formula about the integrality gap for MILP and 0-1 knapsack integer programing model
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 < er...@amsterdamoptimization.com> 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 > er...@amsterdamoptimization.com > http://amsterdamoptimization.com > > > On Thu, Dec 3, 2015 at 12:35 PM, usa usa 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 < >> 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 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
Re: [Help-glpk] the theoretic formula about the integrality gap for MILP and 0-1 knapsack integer programing model
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 er...@amsterdamoptimization.com http://amsterdamoptimization.com On Thu, Dec 3, 2015 at 12:35 PM, usa usa 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 < > 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 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
Re: [Help-glpk] the theoretic formula about the integrality gap for MILP and 0-1 knapsack integer programing model
Hi, Heinrich, On the link, what is formula for "best_mip" ? Given an integer programming model, how to make sure that the "best_mip" is the best estimation for the model without solving it ? Thanks Regards David On Thu, Dec 3, 2015 at 6:09 AM, wrote: > Hello David, > > see > https://en.wikibooks.org/wiki/GLPK/Known_issues#MIP_gap_reporting > > Best regards > > Heinrich Schuchardt > > -Ursprüngliche Nachricht- > Gesendet: Donnerstag, 03 Dezember 2015 um 06:10:20 Uhr > Von: "usa usa" > An: help-glpk@gnu.org > Betreff: [Help-glpk] the theoretic formula about the integrality gap for > MILP and 0-1 knapsack integer programing model > 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
Re: [Help-glpk] the theoretic formula about the integrality gap for MILP and 0-1 knapsack integer programing model
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 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
Re: [Help-glpk] the theoretic formula about the integrality gap for MILP and 0-1 knapsack integer programing model
Hello David, see https://en.wikibooks.org/wiki/GLPK/Known_issues#MIP_gap_reporting Best regards Heinrich Schuchardt -Ursprüngliche Nachricht- Gesendet: Donnerstag, 03 Dezember 2015 um 06:10:20 Uhr Von: "usa usa" An: help-glpk@gnu.org Betreff: [Help-glpk] the theoretic formula about the integrality gap for MILP and 0-1 knapsack integer programing model 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
Re: [Help-glpk] the theoretic formula about the integrality gap for MILP and 0-1 knapsack integer programing model
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 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
