On the complexity of sequentially lifting cover inequalities for the knapsack polytope

DOI10.1007/s11425-019-9538-1zbMath1467.90022arXiv1811.10010OpenAlexW3016497569MaRDI QIDQ829120

Yu-Hong Dai, Wei-Kun Chen

Publication date: 5 May 2021

Published in: Science China. Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1811.10010

zbMATH Keywords

complexityinteger programminglifting problemsequentially lifted cover inequality

Mathematics Subject Classification ID

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

Related Items

Lifting for the integer knapsack cover polyhedron

Cites Work

• Unnamed Item
• Unnamed Item
• Cover and pack inequalities for (mixed) integer programming
• The complexity of lifted inequalities for the knapsack problem
• The complexity of cover inequality separation
• On splittable and unsplittable flow capacitated network design arc-set polyhedra.
• Polyhedral results for the edge capacity polytope.
• Sequence independent lifting in mixed integer programming
• On lifted cover inequalities: a new lifting procedure with unusual properties
• Separation algorithms for 0-1 knapsack polytopes
• Easily Computable Facets of the Knapsack Polytope
• Integer Programming
• Solving Large-Scale Zero-One Linear Programming Problems
• Improving LP-Representations of Zero-One Linear Programs for Branch-and-Cut
• Technical Note—A Note on Zero-One Programming
• 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
• Lifted Cover Inequalities for 0-1 Integer Programs: Complexity
• Solving Mixed Integer Programming Problems Using Automatic Reformulation