A 3-Slope Theorem for the infinite relaxation in the plane

• 成果类型: Article
• 署名作者: Cornuejols, Gerard; Molinaro, Marco
• 署名单位: Carnegie Mellon University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-012-0562-7
• 发表日期: 2013
• 页码: 83-105
• 关键词: tableau

摘要

In this paper we consider the infinite relaxation of the corner polyhedron with 2 rows. For the 1-row case, Gomory and Johnson proved in their seminal paper a sufficient condition for a minimal function to be extreme, the celebrated 2-Slope Theorem. Despite increased interest in understanding the multiple row setting, no generalization of this theorem was known for this case. We present an extension of the 2-Slope Theorem for the case of 2 rows by showing that minimal 3-slope functions satisfying an additional regularity condition are facets (and hence extreme). Moreover, we show that this regularity condition is necessary, unveiling a structure which is only present in the multi-row setting.