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 13:49:56 -0500

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 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
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 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