Optimization Online


Bounds and Algorithms for the Knapsack Problem with Conflict Graph

Andrea Bettinelli (andrea.bettinelli***at***unibo.it)
Valentina Cacchiani (valentina.cacchiani***at***unibo.it)
Enrico Malaguti (enrico.malaguti***at***unibo.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 Branch-and-Bound approach to derive optimal solutions to the KPCG in short computing times. Alternative dual bound procedures are compared, as well as different branching strategies, and new effective ones are proposed. Extensive computational experiments are reported, showing that the proposed method outperforms an existing approach from the literature and a Mixed Integer Programming formulation 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: OR-14-16, DEIS, University of Bologna


Entry Submitted: 06/23/2014
Entry Accepted: 06/23/2014
Entry Last Modified: 04/02/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society