A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph
From MaRDI portal
Publication:4599315
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
combinatorial optimizationcomputational experimentsbranch and boundknapsack problemmaximum weight stable set problem
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)
Related Items
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.
