A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph
Andrea Bettinelli (andrea.bettinelliunibo.it)
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 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.
Category 1: Combinatorial Optimization
Citation: tech. rep. OR-15-1 DEI, University of Bologna
Entry Submitted: 04/02/2015
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|