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

[usa usa]

Hi, Heinrich,

On the link, what is formula for "best_mip" ? 

Given an integer programming model, how to make sure that the "best_mip" is the best estimation for the model without solving it ?

Thanks

Regards

David

On Thu, Dec 3, 2015 at 6:09 AM, <address@hidden> wrote:

Hello David,

see
https://en.wikibooks.org/wiki/GLPK/Known_issues#MIP_gap_reporting

Best regards

Heinrich Schuchardt

-----Ursprüngliche Nachricht-----
Gesendet: Donnerstag, 03 Dezember 2015 um 06:10:20 Uhr
Von: "usa usa" <address@hidden>
An: address@hidden
Betreff: [Help-glpk] the theoretic formula about the integrality gap for MILP and 0-1 knapsack integer programing model

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