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 14:59:05 -0500

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