A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts
From MaRDI portal
Publication:2029024
DOI10.1016/j.ejor.2020.07.023zbMath1487.90546OpenAlexW3045117486MaRDI QIDQ2029024
Fabio Furini, Pablo San Segundo, Stefano Coniglio
Publication date: 3 June 2021
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/10261/229689
branch-and-bound algorithmcombinatorial optimizationmaximum weighted clique problemknapsack problem with conflicts
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, Multiple-choice knapsack constraint in graphical models, A matheuristic for a customer assignment problem in direct marketing, Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming, A threshold search based memetic algorithm for the disjunctively constrained knapsack problem, Cover by disjoint cliques cuts for the knapsack problem with conflicting items, Bin Packing Problem with Time Lags, 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, Features for the 0-1 knapsack problem based on inclusionwise maximal solutions, Fair allocation of indivisible items with conflict graphs, A branch-and-cut algorithm for the edge interdiction clique problem, On the exact separation of cover inequalities of maximum-depth
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Infra-chromatic bound for exact maximum clique search
- Strong lift-and-project cutting planes for the stable set problem
- Clique-based facets for the precedence constrained knapsack problem
- A branch and cut solver for the maximum stable set problem
- An exact bit-parallel algorithm for the maximum clique problem
- An O(n) algorithm for the linear multiple choice knapsack problem and related problems
- Bilevel programming: a survey
- An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
- Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem
- The ellipsoid method and its consequences in combinatorial optimization
- An upper bound for the zero-one knapsack problem and a branch and bound algorithm
- A multi-KP modeling for the maximum-clique problem
- A combinatorial column generation algorithm for the maximum stable set problem
- A minimal algorithm for the multiple-choice knapsack problem
- Local branching
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Foundations of bilevel programming
- On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem
- The maximum clique interdiction problem
- General cut-generating procedures for the stable set polytope
- A new upper bound for the maximum weight clique problem
- A nonconvex quadratic optimization approach to the maximum edge weight clique problem
- On the use of intersection cuts for bilevel optimization
- An improved bit parallel exact maximum clique algorithm
- Maximum-weight stable sets and safe lower bounds for graph coloring
- A new branch-and-bound algorithm for the maximum weighted clique problem
- On integer and bilevel formulations for the \(k\)-vertex cut problem
- Speeding up branch and bound algorithms for solving the maximum clique problem
- Relaxed approximate coloring in exact maximum clique search
- A combinatorial branch-and-bound algorithm for box search
- A new branch-and-bound algorithm for the maximum edge-weighted clique problem
- Coordinated cutting plane generation via multi-objective separation
- An algorithm for the disjunctively constrained knapsack problem
- A review on algorithms for maximum clique problems
- Algorithms for the Bin Packing Problem with Conflicts
- A Branch-and-Price Algorithm for the Bin Packing Problem with Conflicts
- Ellipsoidal Relaxations of the Stable Set Problem: Theory and Algorithms
- Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
- The Knapsack Problem with Conflict Graphs
- An O(n) algorithm for the multiple-choice knapsack linear program
- A reactive local search-based algorithm for the disjunctively constrained knapsack problem
- A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
- The Multiple-Choice Knapsack Problem
- Bilevel Programming Approaches to the Computation of Optimistic and Pessimistic Single-Leader-Multi-Follower Equilibria.
- A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph
- A New General-Purpose Algorithm for Mixed-Integer Bilevel Linear Programs
- Reducibility among Combinatorial Problems
- Incremental Upper Bound for the Maximum Clique Problem
- A branch-and-cut algorithm for the maximum cardinality stable set problem
