Intersection Cuts with Infinite Split Rank

• 成果类型: Article
• 署名作者: Basu, Amitabh; Cornuejols, Gerard; Margot, Francois
• 署名单位: University of California System; University of California Davis; Carnegie Mellon University; Aix-Marseille Universite
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1110.0522
• 发表日期: 2012
• 页码: 21-40
• 关键词: INEQUALITIES

摘要

We consider mixed-integer linear programs where free integer variables are expressed in terms of nonnegative continuous variables. When this model only has two integer variables, Dey and Louveaux characterized the intersection cuts that have infinite split rank. We show that, for any number of integer variables, the split rank of an intersection cut generated from a rational lattice-free polytope L is finite if and only if the integer points on the boundary of L satisfy a certain 2-hyperplane property. The Dey-Louveaux characterization is a consequence of this more general result.