Article ID: | iaor20051104 |
Country: | Germany |
Volume: | 98 |
Issue: | 1/3 |
Start Page Number: | 145 |
End Page Number: | 175 |
Publication Date: | Jan 2003 |
Journal: | Mathematical Programming |
Authors: | Atamtrk A. |
Keywords: | knapsack problem |
We study the mixed-integer knapsack polyhedron, that is, the convex hull of the mixed-integer set defined by an arbitrary linear inequality and the bounds on the variables. We describe facet-defining inequalities of this polyhedron that can be obtained through sequential lifting of inequalities containing a single integer variable. These inequalities strengthen and/or generalize known inequalities for several special cases. We report computational results on using the inequalities as cutting planes for mixed-integer programming.