On the facets of the mixed-integer knapsack polyhedron

Alper Atamturk (atamturkieor.berkeley.edu)

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.

Keywords:

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Citation: Mathematical Programming 98, 145-175, 2003

Download:

Entry Submitted: 02/27/2003
Entry Accepted: 02/27/2003
Entry Last Modified: 04/15/2008

Modify/Update this entry