Cover by disjoint cliques cuts for the knapsack problem with conflicting items

DOI10.1016/J.ORL.2021.10.001MaRDI QIDQ2670441zbMATH OpenOpenAlexFDO

Authors Thiago Alcântara Luiz, Haroldo G. Santos, Eduardo Uchoa

Publication date 11 March 2022

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.orl.2021.10.001

zbMATH Keywords

clique inequalitycombinatorial cutscover inequalityknapsack problemlifting

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Recommendations

• Optimization algorithms for the disjunctively constrained knapsack problem
• A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts
• The Knapsack Problem with Conflict Graphs
• A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph
• scientific article; zbMATH DE number 1187156

Cites work

• A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts
• A polyhedral study on 0-1 knapsack problems with set packing constraints
• A polyhedral study on \(0\)-\(1\) knapsack problems with disjoint cardinality constraints: facet-defining inequalities by sequential lifting
• A polyhedral study on \(0\)-\(1\) knapsack problems with disjoint cardinality constraints: strong valid inequalities by sequence-independent lifting
• A strengthened formulation and cutting planes for the open pit mine production scheduling problem
• Faces for a linear inequality in 0–1 variables
• Facets of the knapsack polytope
• Facets of the Knapsack Polytope From Minimal Covers
• Finding a Maximum Independent Set
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• Lifted cover facets of the 0-1 knapsack polytope with GUB constraints
• Lifting cover inequalities for the precedence-constrained knapsack problem
• Noncommercial software for mixed-integer linear programming
• On lifted cover inequalities: a new lifting procedure with unusual properties
• On the facial structure of set packing polyhedra
• Optimization algorithms for the disjunctively constrained knapsack problem
• Solving Airline Crew Scheduling Problems by Branch-and-Cut
• Strong bounds for resource constrained project scheduling: preprocessing and cutting planes
• Valid inequalities for a single constrained 0-1 MIP set intersected with a conflict graph
• Wheel inequalities for stable set polytopes

Cited in

(5)

• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• The knapsack problem with forfeit sets
• Knapsack: connectedness, path, and shortest-path
• Relaxations and cutting planes for linear programs with complementarity constraints
• Knapsack with vertex cover, set cover, and hitting set

This page was built for publication: Cover by disjoint cliques cuts for the knapsack problem with conflicting items

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