Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem

DOI10.1016/j.cor.2005.10.004zbMath1141.90512OpenAlexW2084894096MaRDI QIDQ875412

M. Michrafy, Mhand Hifi

Publication date: 13 April 2007

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2005.10.004

zbMATH Keywords

combinatorial optimizationbranch and bounddichotomous searchknapsacksreduction strategiesvalid cuts

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (16)

A modified descent method-based heuristic for binary quadratic knapsack problems with conflict graphs ⋮ Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ Procedures for the bin packing problem with precedence constraints ⋮ Branch-and-cut for linear programs with overlapping SOS1 constraints ⋮ A Fast Large Neighborhood Search for Disjunctively Constrained Knapsack Problems ⋮ A threshold search based memetic algorithm for the disjunctively constrained knapsack problem ⋮ Min-Sup-Min Robust Combinatorial Optimization with Few Recourse Solutions ⋮ Responsive strategic oscillation for solving the disjunctively constrained knapsack problem ⋮ A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph ⋮ Probabilistic Tabu search with multiple neighborhoods for the Disjunctively Constrained Knapsack Problem ⋮ Branch-and-price and beam search algorithms for the variable cost and size bin packing problem with optional items ⋮ 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 Fast Algorithm for Knapsack Problem with Conflict Graph

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An algorithm for the solution of the 0-1 knapsack problem
• Using Decomposition Techniques and Constraint Programming for Solving the Two-Dimensional Bin-Packing Problem
• Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
• A reactive local search-based algorithm for the disjunctively constrained knapsack problem
• An Algorithm for Large Zero-One Knapsack Problems
• Multistage Cutting Stock Problems of Two and More Dimensions
• Discrete-Variable Extremum Problems
• The Theory and Computation of Knapsack Functions

This page was built for publication: Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem