Optimization algorithms for the disjunctively constrained knapsack problem

DOI10.1007/s00500-016-2465-7zbMath1398.90131OpenAlexW2567449761MaRDI QIDQ1797814

Raouia Taktak, Mariem Ben Salem, Hanêne Ben-Abdallah, Ali Ridha Mahjoub

Publication date: 22 October 2018

Published in: Soft Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00500-016-2465-7

zbMATH Keywords

polytopeknapsack problemseparationbranch-and-cutfacetdisjunctive constraints

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items

Knapsack problems -- an overview of recent advances. I: Single knapsack problems, A threshold search based memetic algorithm for the disjunctively constrained knapsack problem, Cover by disjoint cliques cuts for the knapsack problem with conflicting items, 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

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A polyhedral study on \(0\)-\(1\) knapsack problems with disjoint cardinality constraints: facet-defining inequalities by sequential lifting
• Exploiting nested inequalities and surrogate constraints
• Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem
• The submodular knapsack polytope
• Polyhedral results for the precedence-constrained knapsack problem
• Geometric algorithms and combinatorial optimization
• The complexity of cover inequality separation
• On the \(0/1\) knapsack polytope
• A polyhedral study of the cardinality constrained knapsack problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A scheme for exact separation of extended cover inequalities and application to multidimensional knapsack problems
• Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem
• Separation algorithms for 0-1 knapsack polytopes
• Core Problems in Knapsack Algorithms
• Easily Computable Facets of the Knapsack Polytope
• Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
• The Knapsack Problem with Conflict Graphs
• Solving Large-Scale Zero-One Linear Programming Problems
• Generalizations of Cliques, Odd Cycles and Anticycles and Their Relation to Independence System Polyhedra
• A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
• Faces for a linear inequality in 0–1 variables
• Facet of regular 0–1 polytopes
• Facets of the knapsack polytope
• Facets of the Knapsack Polytope From Minimal Covers
• A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph
• Solving Mixed Integer Programming Problems Using Automatic Reformulation
• Properties of vertex packing and independence system polyhedra