On the exact separation of cover inequalities of maximum-depth

DOI10.1007/S11590-021-01741-0zbMATH Open1487.90544OpenAlexW3159420182MaRDI QIDQ2115307FDOQ2115307

Authors: Daniele Catanzaro, S. Coniglio, Fabio Furini 

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

Recommendations

• A scheme for exact separation of extended cover inequalities and application to multidimensional knapsack problems
• On separating cover inequalities for the multidimensional knapsack problem
• On the complexity of separation from the knapsack polytope
• Separation algorithms for 0-1 knapsack polytopes
• The precedence constrained knapsack problem: separating maximally violated inequalities

zbMATH Keywords

dynamic programmingknapsack problemcover inequalitiesmixed integer nonlinear programmingcutting plane generation

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (2)

• On the complexity of separating cutting planes for the knapsack polytope
• A scheme for exact separation of extended cover inequalities and application to multidimensional knapsack problems

Uses Software

• SCIP
• OR-Library
• Knapsack

This page was built for publication: On the exact separation of cover inequalities of maximum-depth

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