| Article ID: | iaor1997331 |
| Country: | Netherlands |
| Volume: | 16 |
| Issue: | 5 |
| Start Page Number: | 255 |
| End Page Number: | 263 |
| Publication Date: | Dec 1994 |
| Journal: | Operations Research Letters |
| Authors: | Nemhauser George L., Vance Pamela H. |
| Keywords: | knapsack problem |
Facet-defining inequalities lifted from minimal covers are used as strong cutting planes in algorithms for solving 0-1 integer programming problems. In this paper the authorts extend the result of Balas and Zemel by giving a set of inequalities that determines the lifting coefficients of facet-defining inequalities of the 0-1 knapsack polytope for any ordering of the variables to be lifted. They further generalize the result to obtain facet-defining inequalities for the 0-1 knapsack problem with generalized upper bound constraints.