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

[Erwin Kalvelagen]

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