On the facets of the mixed-integer knapsack polyhedron

On the facets of the mixed-integer knapsack polyhedron

0.00 Avg rating0 Votes
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:
Keywords: knapsack problem
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.