|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:35:23 -0500|
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 optimalOn 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
|[Prev in Thread]||Current Thread||[Next in Thread]|