help-glpk
[Top][All Lists]

## Re: [Help-glpk] the theoretic formula about the integrality gap for MILP

 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 12:35:09 -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 !

David

On Thu, Dec 3, 2015 at 12:20 AM, Erwin Kalvelagen 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
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