Clique-based facets for the precedence constrained knapsack problem

Title: Clique-based facets for the precedence constrained knapsack problem
Creator: Boland, Natashia; Bley, Andreas; Fricke, Christopher; Froyland, Gary; Sotirov, Renata
Relation: Mathematical Programming Vol. 133, p. 481-511
Publisher Link: http://dx.doi.org/10.1007/s10107-010-0438-7
Publisher: Springer
Resource Type: journal article
Date: 2012
Description: 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.
Subject: precedence constrained knapsack problem; clique inequalities; integer programming; PCKP
Identifier: http://hdl.handle.net/1959.13/939408
Identifier: uon:12800
Identifier: ISSN:0025-5610
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format