The complexity of cover inequality separation

DOI10.1016/S0167-6377(98)00025-XzbMath0957.90094WikidataQ127845863 ScholiaQ127845863MaRDI QIDQ1306471

Diego Klabjan, Nemhauser, George I., Craig A. Tovey

Publication date: 2 April 2001

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

zbMATH Keywords

integer programmingcover inequalitiesseparation problem

Mathematics Subject Classification ID

Integer programming (90C10)

Related Items (20)

Implicit cover inequalities ⋮ Knapsack polytopes: a survey ⋮ On the complexity of sequentially lifting cover inequalities for the knapsack polytope ⋮ Cutting planes for the multistage stochastic unit commitment problem ⋮ Separation algorithms for 0-1 knapsack polytopes ⋮ On the complexity of separation from the knapsack polytope ⋮ A cut-and-solve based algorithm for the single-source capacitated facility location problem ⋮ On inequalities with bounded coefficients and pitch for the min knapsack polytope ⋮ Packing, partitioning, and covering symresacks ⋮ New classes of facets for complementarity knapsack problems ⋮ Multi-cover inequalities for totally-ordered multiple knapsack sets: theory and computation ⋮ Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem ⋮ Strengthening convex relaxations of 0/1-sets using Boolean formulas ⋮ Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes ⋮ Branch-and-cut-and-price algorithm for the constrained-routing and spectrum assignment problem ⋮ Optimization algorithms for the disjunctively constrained knapsack problem ⋮ Sparsity of integer formulations for binary programs ⋮ Pitch, extension complexity, and covering problems ⋮ Simple lifted cover inequalities and hard knapsack problems ⋮ On the exact separation of cover inequalities of maximum-depth

Cites Work

• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• Solving Large-Scale Zero-One Linear Programming Problems
• Solving Multiple Knapsack Problems by Cutting Planes
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The complexity of cover inequality separation