On the exact separation of cover inequalities of maximum-depth

DOI10.1007/s11590-021-01741-0zbMath1487.90544OpenAlexW3159420182MaRDI QIDQ2115307

Daniele Catanzaro, Fabio Furini, Stefano Coniglio

Publication date: 15 March 2022

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-021-01741-0

zbMATH Keywords

dynamic programmingknapsack problemmixed integer nonlinear programmingcover inequalitiescutting plane generation

Mathematics Subject Classification ID

Mixed integer programming (90C11) Combinatorial optimization (90C27) Dynamic programming (90C39)

Uses Software

• SCIP
• OR-Library
• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bin packing and cutting stock problems: mathematical models and exact algorithms
• Lexicography and degeneracy: Can a pure cutting plane algorithm work?
• SCIP: solving constraint integer programs
• Knapsack polytopes: a survey
• Algorithms to separate \(\{0,\frac{1}{2}\}\)-Chvátal-Gomory cuts
• Integrated airline scheduling
• A computational study of exact knapsack separation for the generalized assignment problem
• A genetic algorithm for the multidimensional knapsack problem
• Arbitrary-norm separating plane
• The complexity of cover inequality separation
• The Steiner tree problem. II: Properties and classes of facets
• \(k\)-plane clustering
• Exact approaches for the knapsack problem with setups
• On the product knapsack problem
• An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem
• A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts
• A distance-based point-reassignment heuristic for the \(k\)-hyperplane clustering problem
• A lexicographic pricer for the fractional bin packing problem
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• Coordinated cutting plane generation via multi-objective separation
• Separation algorithms for 0-1 knapsack polytopes
• Embedding {0, ½}-Cuts in a Branch-and-Cut Framework: A Computational Study
• The Multidimensional Knapsack Problem: Structure and Algorithms
• Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
• The Knapsack Problem with Conflict Graphs
• Heuristic and Exact Algorithms for the Interval Min–Max Regret Knapsack Problem
• Solving Large-Scale Zero-One Linear Programming Problems
• Mixed 0-1 Programming by Lift-and-Project in a Branch-and-Cut Framework
• A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph