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

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

Knapsack Problem
Clique
Facet
Decomposition
Cover
Precedence Constraints
Knapsack
Decomposition Techniques
Network Design
Polyhedron
Mining
Manufacturing

Cite this

Bley, A., Boland, N., Fricke, C., Froyland, G., & Sotirov, R. (2012). Clique-based facets for the precedence constrained knapsack problem. Mathematical Programming, 133(1), 481-511.
Bley, A. ; Boland, N. ; Fricke, C. ; Froyland, G. ; Sotirov, R. / Clique-based facets for the precedence constrained knapsack problem. In: Mathematical Programming. 2012 ; Vol. 133, No. 1. pp. 481-511.
@article{d6fd82aa5c174a87b7d8c201b0a69717,
title = "Clique-based facets for the precedence constrained knapsack problem",
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.",
author = "A. Bley and N. Boland and C. Fricke and G. Froyland and R. Sotirov",
year = "2012",
language = "English",
volume = "133",
pages = "481--511",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer",
number = "1",

}

Bley, A, Boland, N, Fricke, C, Froyland, G & Sotirov, R 2012, 'Clique-based facets for the precedence constrained knapsack problem', Mathematical Programming, vol. 133, no. 1, pp. 481-511.

Clique-based facets for the precedence constrained knapsack problem. / Bley, A.; Boland, N.; Fricke, C.; Froyland, G.; Sotirov, R.

In: Mathematical Programming, Vol. 133, No. 1, 2012, p. 481-511.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Clique-based facets for the precedence constrained knapsack problem

AU - Bley, A.

AU - Boland, N.

AU - Fricke, C.

AU - Froyland, G.

AU - Sotirov, R.

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

M3 - Article

VL - 133

SP - 481

EP - 511

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 1

ER -