Lifting 2-integer knapsack inequalities

Agostinho Agra (aagramat.ua.pt)
Miguel Constantino (miguel.constantinofc.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