Optimization Online


Lifting 2-integer knapsack inequalities

Agostinho Agra (aagra***at***mat.ua.pt)
Miguel Constantino (miguel.constantino***at***fc.ul.pt)

Abstract: In this paper we discuss the generation of strong valid inequalities for (mixed) integer knapsack sets based on lifting of valid inequalities for basic knapsack sets with two integer variables (and one continuous variable). The description of the basic polyhedra can be made in polynomial time. We use superadditive valid functions in order to obtain sequence independent lifting.

Keywords: mixed integer programming, lifting, superadditivity

Category 1: Integer Programming

Citation: C.I.O. University of Lisbon

Download: [PDF]

Entry Submitted: 08/16/2003
Entry Accepted: 08/20/2003
Entry Last Modified: 10/01/2003

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