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

[usa usa]

Hi, Andrews,

For one numerical instance, your method works.

What I need is the mathematical formula for the gap.

Example, given IP :

max. C x W

s.t     A x W <= B

        x is 0, 1 integer

What is gap between the IP and its Linear programming relaxation  ?

the gap can only be expressed by A, B, C and other constants if necessary.

Also, what is "any (not LP) relaxation of MIP" in your reply ?

What does the "LP" mean here ?

Thanks

On Thu, Dec 3, 2015 at 2:52 PM, Andrew Makhorin <address@hidden> wrote:

>                 How to estimate the "bestpossible" and "epsilon"
>                 without solving an integer programming model ?

Find any integer feasible solution to MIP (not solving MIP exactly),
e.g. with a primal heuristic--it gives you "bestfound".

>
>
>                 How to estimate the "bestpossible" and "epsilon"
>                 without solving an linear programming model ?

Find an optimal solution to any (not LP) relaxation of MIP--it gives you
"bestpossible".

Take "epsilon" as a smallest floating-point number such that 1+eps > 1.