Sufficiency of cut-generating functions

• 成果类型: Article
• 署名作者: Cornuejols, Gerard; Wolsey, Laurence; Yildiz, Sercan
• 署名单位: Carnegie Mellon University; Universite Catholique Louvain
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-014-0780-2
• 发表日期: 2015
• 页码: 643-651
• 关键词: INEQUALITIES

摘要

The concept of cut-generating function has its origin in the work of Gomory and Johnson from the 1970s. It has received renewed attention in the past few years. Recently Conforti, Cornu,jols, Daniilidis, Lemar,chal, and Malick proposed a general framework for studying cut-generating functions. However, they gave an example showing that not all cuts can be produced by cut-generating functions in this framework. They conjectured a natural condition under which cut-generating functions might be sufficient. This note settles this open problem.