A fast algorithm for knapsack problem with conflict graph

DOI10.1142/S021759592150010XMaRDI QIDQ5024916zbMATH OpenOpenAlexFDO

Authors

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

branch-and-boundcombinatorial optimizationknapsack problem with conflict graphmaximum weight stable set problem

Mathematics Subject Classification ID

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

Recommendations

• A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph
• A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts
• The Knapsack Problem with Conflict Graphs
• Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width
• Optimization algorithms for the disjunctively constrained knapsack problem

Cites work

• A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph
• A new upper bound for the maximum weight clique problem
• A reactive local search-based algorithm for the disjunctively constrained knapsack problem
• An algorithm for the disjunctively constrained knapsack problem
• Benchmarking optimization software with performance profiles.
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• Local branching
• Maximum-weight stable sets and safe lower bounds for graph coloring
• Reducibility among combinatorial problems
• Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem
• The Knapsack Problem with Conflict Graphs

Cited in

(8)

• A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts
• Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width
• The Knapsack Problem with Conflict Graphs
• A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph
• Matheuristic fixed set search applied to the multidimensional knapsack problem and the knapsack problem with forfeit sets
• Hybridizing carousel greedy and kernel search: a new approach for the maximum flow problem with conflict constraints
• Bi-objective knapsack problem with conflicts
• A modified descent method-based heuristic for binary quadratic knapsack problems with conflict graphs

Describes a project that uses

Uses Software

• CPLEX

This page was built for publication: A fast algorithm for knapsack problem with conflict graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5024916)