Optimization Online


On the facets of the mixed-integer knapsack polyhedron

Alper Atamturk (atamturk***at***ieor.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.


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

Citation: Mathematical Programming 98, 145-175, 2003


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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society