Optimization Online


Clique-based facets for the precedence constrained knapsack problem

Natashia Boland (Natashia.Boland***at***newcastle.edu.au)
Christopher Fricke (fricke***at***ms.unimelb.edu.au)
Gary Froyland (g.froyland***at***unsw.edu.au)
Renata Sotirov (r.sotirov***at***uvt.nl)
Andreas Bley (bley***at***zib.de)

Abstract: We consider a knapsack problem with precedence constraints imposed on pairs of items, known as the precedence constrained knapsack problem (PCKP). This problem has applications in management and machine scheduling, and also appears as a subproblem in decomposition techniques for network design and other related problems. We present a new approach for determining facets of the PCKP polyhedron based on clique inequalities. A comparison with existing techniques, that lift knapsack cover inequalities for the PCKP, is also presented. It is shown that the clique-based approach generates facets that cannot be found through the existing cover-based approaches, and that the addition of clique-based inequalities for the PCKP can be computationally beneficial.

Keywords: Precedence constrained knapsack problem; Clique inequalities; Integer programming

Category 1: Integer Programming (0-1 Programming )

Category 2: Combinatorial Optimization (Polyhedra )

Citation: Department of Mathematics and Statistics, University of Melbourne, Victoria, Australia 3010, December 2005

Download: [PDF]

Entry Submitted: 01/30/2006
Entry Accepted: 01/31/2006
Entry Last Modified: 11/01/2009

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