A Fast Algorithm for Knapsack Problem with Conflict Graph

DOI10.1142/S021759592150010XzbMath1484.90095OpenAlexW3128148487MaRDI QIDQ5024916

No author found.

Publication date: 1 February 2022

Published in: Asia-Pacific Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s021759592150010x

zbMATH Keywords

combinatorial optimizationbranch-and-boundmaximum weight stable set problemknapsack problem with conflict graph

Mathematics Subject Classification ID

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

Uses Software

• CPLEX

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem
• Local branching
• A new upper bound for the maximum weight clique problem
• Maximum-weight stable sets and safe lower bounds for graph coloring
• An algorithm for the disjunctively constrained knapsack problem
• The Knapsack Problem with Conflict Graphs
• A reactive local search-based algorithm for the disjunctively constrained knapsack problem
• A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph
• Reducibility among Combinatorial Problems
• Benchmarking optimization software with performance profiles.

This page was built for publication: A Fast Algorithm for Knapsack Problem with Conflict Graph