Clique-based facets for the precedence constrained knapsack problem

A. Bley, N. Boland, C. Fricke, G. Froyland, R. Sotirov

Research output: Contribution to journalArticleScientificpeer-review

7 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)481-511
JournalMathematical Programming
Volume133
Issue number1
Publication statusPublished - 2012

Fingerprint Dive into the research topics of 'Clique-based facets for the precedence constrained knapsack problem'. Together they form a unique fingerprint.

  • Cite this