Optimization Online


Separation Algorithms for 0-1 Knapsack Polytopes

Konstantinos Kaparis (k.kaparis***at***soton.ac.uk)
Adam Letchford (A.N.Letchford***at***lancaster.ac.uk)

Abstract: Valid inequalities for 0-1 knapsack polytopes often prove useful when tackling hard 0-1 Linear Programming problems. To use such inequalities effectively, one needs separation algorithms for them, i.e., routines for detecting when they are violated. We show that the separation problems for the so-called extended cover and weight inequalities can be solved exactly in O(nb) time and O((n + a_max)b) time, respectively, where n is the number of items, b is the knapsack capacity and a_max is the largest item weight. We also present fast and effective separation heuristics for the extended cover and lifted cover inequalities. Finally, we present a new exact separation algorithm for the 0-1 knapsack polytope itself, which is faster than existing methods. Extensive computational results are also given.

Keywords: integer programming, branch-and-cut, knapsack problems

Category 1: Integer Programming (0-1 Programming )

Category 2: Integer Programming (Cutting Plane Approaches )

Category 3: Combinatorial Optimization (Polyhedra )

Citation: K. Kaparis & A.N. Letchford (2010) Separation algorithms for 0-1 knapsack polytopes. Math. Program., 124(1-2), 69-91.


Entry Submitted: 06/07/2007
Entry Accepted: 06/07/2007
Entry Last Modified: 02/10/2011

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