Separation algorithms for 0-1 knapsack polytopes

• 成果类型: Article
• 署名作者: Kaparis, Konstantinos; Letchford, Adam N.
• 署名单位: Lancaster University; University of Southampton
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-010-0359-5
• 发表日期: 2010
• 页码: 69-91
• 关键词: lifted cover inequalities; FENCHEL CUTTING PLANES; facets

摘要

Valid inequalities for 0-1 knapsack polytopes often prove useful when tackling hard 0-1 Linear Programming problems. To generate such inequalities, one needs separation algorithms for them, i.e., routines for detecting when they are violated. We present new exact and heuristic separation algorithms for several classes of inequalities, namely lifted cover, extended cover, weight and lifted pack inequalities. Moreover, we show how to improve a recent separation algorithm for the 0-1 knapsack polytope itself. Extensive computational results, on MIPLIB and OR Library instances, show the strengths and limitations of the inequalities and algorithms considered.