A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph

DOI10.1287/ijoc.2016.0742zbMath1386.90123OpenAlexW2620796999MaRDI QIDQ4599315

Valentina Cacchiani, Enrico Malaguti, Andrea Bettinelli

Publication date: 29 December 2017

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/f85385b74ea698ceb4a5a80611b7de8a880f311d

zbMATH Keywords

combinatorial optimizationcomputational experimentsbranch and boundknapsack problemmaximum weight stable set problem

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Related Items (26)

Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ Two-stage three-machine assembly scheduling problem with sum-of-processing-times-based learning effect ⋮ On the product knapsack problem ⋮ An exact algorithm for parallel machine scheduling with conflicts ⋮ Multiple-choice knapsack constraint in graphical models ⋮ A matheuristic for a customer assignment problem in direct marketing ⋮ Models and Algorithms for the Bin-Packing Problem with Minimum Color Fragmentation ⋮ A threshold search based memetic algorithm for the disjunctively constrained knapsack problem ⋮ Optimal selection of touristic packages based on user preferences during sports mega-events ⋮ Exact algorithms to minimize makespan on single and parallel batch processing machines ⋮ Hybridizing adaptive large neighborhood search with kernel search: a new solution approach for the nurse routing problem with incompatible services and minimum demand ⋮ Minimum cost flow problem with conflicts ⋮ Bin Packing Problem with Time Lags ⋮ Pseudo-polynomial algorithms for solving the knapsack problem with dependencies between items ⋮ The knapsack problem with forfeit sets ⋮ Responsive strategic oscillation for solving the disjunctively constrained knapsack problem ⋮ CliSAT: a new exact algorithm for hard maximum clique problems ⋮ Maximum weight perfect matching problem with additional disjunctive conflict constraints ⋮ Probabilistic Tabu search with multiple neighborhoods for the Disjunctively Constrained Knapsack Problem ⋮ Exact solution algorithms for the maximum flow problem with additional conflict constraints ⋮ A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts ⋮ Optimization algorithms for the disjunctively constrained knapsack problem ⋮ Dual Inequalities for Stabilized Column Generation Revisited ⋮ A New Branch-and-Price-and-Cut Algorithm for One-Dimensional Bin-Packing Problems ⋮ A Fast Algorithm for Knapsack Problem with Conflict Graph ⋮ On the exact separation of cover inequalities of maximum-depth

Cites Work

• Unnamed Item
• Unnamed Item
• An exact approach for the vertex coloring problem
• Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem
• An exact algorithm for the maximum clique problem
• Local branching
• Heuristics and lower bounds for the bin packing problem with conflicts
• Maximum-weight stable sets and safe lower bounds for graph coloring
• An algorithm for the disjunctively constrained knapsack problem
• Algorithms for the Bin Packing Problem with Conflicts
• A Branch-and-Price Algorithm for the Bin Packing Problem with Conflicts
• The Knapsack Problem with Conflict Graphs
• A reactive local search-based algorithm for the disjunctively constrained knapsack problem
• Reducibility among Combinatorial Problems
• Benchmarking optimization software with performance profiles.

This page was built for publication: A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph