A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph
Andrea Bettinelli (),
Valentina Cacchiani () and
Enrico Malaguti ()
Additional contact information
Andrea Bettinelli: OPTIT Srl, 40026 Imola (BO), Italy
Valentina Cacchiani: Department of Electrical, Electronic, and Information Engineering “Guglielmo Marconi,” Università di Bologna, 40136 Bologna, Italy
Enrico Malaguti: Department of Electrical, Electronic, and Information Engineering “Guglielmo Marconi,” Università di Bologna, 40136 Bologna, Italy
INFORMS Journal on Computing, 2017, vol. 29, issue 3, 457-473
Abstract:
We study the knapsack problem with conflict graph (KPCG), an extension of the 0-1 knapsack problem, in which a conflict graph describing incompatibilities between items is given. The goal of the KPCG is to select the maximum profit set of compatible items while satisfying the knapsack capacity constraint. We present a new branch-and-bound approach to derive optimal solutions to the KPCG in short computing times. Extensive computational experiments are reported showing that, for instances with graph density of 10% and larger, the proposed method outperforms a state-of-the-art approach and mixed-integer programming formulations tackled through a general purpose solver.
Keywords: knapsack problem; maximum weight stable set problem; branch and bound; combinatorial optimization; computational experiments (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (12)
Downloads: (external link)
https://doi.org/10.1287/ijoc.2016.0742 (application/pdf)
Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:29:y:2017:i:3:p:457-473
Access Statistics for this article
More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().