Re: [Help-glpk] the theoretic formula about the integrality gap for MILP and 0-1 knapsack integer programing model

[Erwin Kalvelagen]

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 !

David

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

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
address@hidden
https://lists.gnu.org/mailman/listinfo/help-glpk