|
|||||
|
|
Clique-based facets for the precedence constrained knapsack problem |
|
| Authors: | Natashia Boland Andreas Bley Christopher Fricke Gary Froyland Renata Sotirov |
| Institution: | 1. School of Mathematical and Physical Sciences, University of Newcastle, Callaghan, NSW, 2308, Australia 2. Technical University Berlin, Stra?e des 17. Juni 136, 10623, Berlin, Germany 3. TSG Consulting, Level 11, 350 Collins Street, Melbourne, VIC, 3000, Australia 4. School of Mathematics and Statistics, University of New South Wales, Sydney, NSW, 2052, Australia 5. Universiteit van Tilburg Warandelaan 2, P.O. Box 90153, 5000 LE, Tilburg, The Netherlands |
| 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, for both PCKP instances arising in real applications, and applications in which PCKP appears as an embedded structure. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |