Optimization Online


Clique-based facets for the precedence constrained knapsack problem

Natashia Boland(Natashia.Boland***at***newcastle.edu.au)
Andreas Bley(bley***at***math.tu-berlin.de)
Christopher Fricke(chris.fricke***at***tsgconsulting.com.au)
Gary Froyland(g.froyland***at***unsw.edu.au)
Renata Sotirov(r.sotirov***at***uvt.nl)

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 manufacturing and mining, and also appears as a subproblem in decomposition techniques for network design and 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 (Cutting Plane Approaches )

Citation: School of Mathematical and Physical Sciences, The University of Newcastle, NSW, 2308, Australia, October 2009

Download: [PDF]

Entry Submitted: 10/26/2009
Entry Accepted: 10/26/2009
Entry Last Modified: 10/26/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