Minimal cut-generating functions are nearly extreme

• 成果类型: Article
• 署名作者: Basu, Amitabh; Hildebrand, Robert; Molinaro, Marco
• 署名单位: Johns Hopkins University; International Business Machines (IBM); IBM USA; Pontificia Universidade Catolica do Rio de Janeiro
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-017-1153-4
• 发表日期: 2018
• 页码: 329-349
• 关键词: infinite group relaxation; THEOREM

摘要

We study continuous (strongly) minimal cut generating functions for the model where all variables are integer. We consider both the original Gomory-Johnson setting as well as a recent extension by Yldz and Cornuejols (Math Oper Res 41:1381-1403, 2016). We show that for any continuous minimal or strongly minimal cut generating function, there exists an extreme cut generating function that approximates the (strongly) minimal function as closely as desired. In other words, the extreme functions are dense in the set of continuous (strongly) minimal functions.