Valid inequalities for the multi-dimensional multiple-choice 0-1 knapsack problem

DOI10.1016/j.disopt.2015.03.003zbMath1387.90217OpenAlexW1974903013MaRDI QIDQ1751116

Wilbert E. Wilhelm, Elif Ilke Gokce

Publication date: 24 May 2018

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

Full work available at URL: https://doi.org/10.1016/j.disopt.2015.03.003

zbMATH Keywords

valid inequalitiesmultiple-choice knapsack problem\(\alpha\)-cover inequalitiesmulti-dimensional multiple-choice knapsack problemsequential and sequence-independent lifting

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Boolean programming (90C09)

Related Items (2)

Knapsack polytopes: a survey ⋮ Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems

Cites Work

• Unnamed Item
• A polyhedral study on \(0\)-\(1\) knapsack problems with disjoint cardinality constraints: strong valid inequalities by sequence-independent lifting
• Second-order cover inequalities
• Higher-order cover cuts from zero-one knapsack constraints augmented by two-sided bounding inequalities
• A column generation method for the multiple-choice multi-dimensional knapsack problem
• A note on the knapsack problem with special ordered sets
• Generating cuts from surrogate constraint analysis for zero-one and multiple choice programming
• On the facets of the mixed-integer knapsack polyhedron
• Lifted flow cover inequalities for mixed \(0\)-\(1\) integer programs
• Towards the real time solution of strike force asset allocation problems
• Lifted cover facets of the 0-1 knapsack polytope with GUB constraints
• Sequence independent lifting in mixed integer programming
• A reactive local search-based algorithm for the multiple-choice multi-dimensional knapsack problem
• Valid inequalities for 0-1 knapsacks and MIPs with generalised upper bound constraints
• Solving Large-Scale Zero-One Linear Programming Problems
• Facet of regular 0–1 polytopes
• Facets of the knapsack polytope
• Facets of the Knapsack Polytope From Minimal Covers
• Valid Inequalities and Superadditivity for 0–1 Integer Programs
• Fenchel Cutting Planes for Integer Programs
• Hilbert Bases and the Facets of Special Knapsack Polytopes
• The Sequential Knapsack Polytope
• Sequential and Simultaneous Liftings of Minimal Cover Inequalities for Generalized Upper Bound Constrained Knapsack Polytopes
• Solving Multiple Knapsack Problems by Cutting Planes
• A Facet Generation Procedure for Solving 0/1 Integer Programs

This page was built for publication: Valid inequalities for the multi-dimensional multiple-choice 0-1 knapsack problem