Abstract | ||
---|---|---|
For an integer program, ak-cut is a cutting plane generated by the Gomory mixed integer procedure from a row of the LP tableau after multiplying it by a positive integerk. With this terminology, Gomory mixed integer cuts are just 1-cuts. In this paper, we compare thek-cuts ( k = 2) with Gomory mixed integer cuts. In particular, we prove in the pure case that with exactly 50% probability thek-cuts perform better variable-wise than the Gomory mixed integer cuts. Some computational experiments on knapsack problems are reported to illustrate this property. |
Year | DOI | Venue |
---|---|---|
2003 | 10.1287/ijoc.15.4.385.24893 | INFORMS Journal on Computing |
Keywords | Field | DocType |
lp tableau,gomory mixed integer cut,positive integerk,knapsack problem,pure case,integer program,gomory mixed integer cuts,computational experiment,better variable-wise,gomory mixed integer procedure,probability thek-cuts,integer programming | Integer,Discrete mathematics,Mathematical optimization,Cutting-plane method,Combinatorics,Integer programming,Knapsack problem,Mathematics | Journal |
Volume | Issue | ISSN |
15 | 4 | 1091-9856 |
Citations | PageRank | References |
19 | 1.40 | 7 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Gérard Cornuéjols | 1 | 2390 | 279.95 |
Yanjun Li | 2 | 183 | 12.42 |
Dieter Vandenbussche | 3 | 324 | 17.00 |