|
From: | usa usa |
Subject: | Re: [Help-glpk] the theoretic formula about the integrality gap for MILP and 0-1 knapsack integer programing model |
Date: | Thu, 3 Dec 2015 13:49:56 -0500 |
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
address@hidden
http://amsterdamoptimization.com
----------------------------------------------------------------On Thu, Dec 3, 2015 at 12:35 PM, usa usa <address@hidden> 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 !DavidOn Thu, Dec 3, 2015 at 12:20 AM, Erwin Kalvelagen <address@hidden> 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
address@hidden
http://amsterdamoptimization.com
----------------------------------------------------------------On Thu, Dec 3, 2015 at 12:10 AM, usa usa <address@hidden> wrote:_______________________________________________DavidBest Regards,Any help would be appreciated.I would like to see the formula that express the gap mathematically.Sometimes the gao may be called relative error or approximation ratio.2. 0-1 knapsack integer programing model and its linear programming relaxationHi,I would like to find the theoretic formula about the integrality gap for
1. Mixed integer linear programing model and its linear programming relaxation
Help-glpk mailing list
address@hidden
https://lists.gnu.org/mailman/listinfo/help-glpk
[Prev in Thread] | Current Thread | [Next in Thread] |