
From:  usa usa 
Subject:  Re: [Helpglpk] the theoretic formula about the integrality gap for MILP and 01 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, primaldual simplex algorithm and branchbound 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. 01 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
Helpglpk mailing list
address@hidden
https://lists.gnu.org/mailman/listinfo/helpglpk
[Prev in Thread]  Current Thread  [Next in Thread] 