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 <[email protected]> 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.
>
>
>
_______________________________________________
Help-glpk mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/help-glpk
