On the Chvatal-Gomory closure of a compact convex set

• 成果类型: Article
• 署名作者: Dadush, Daniel; Dey, Santanu S.; Vielma, Juan Pablo
• 署名单位: University System of Georgia; Georgia Institute of Technology; Massachusetts Institute of Technology (MIT); Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-013-0649-9
• 发表日期: 2014
• 页码: 327-348
• 关键词: traveling salesman problem; cuts

摘要

In this paper, we show that the Chvatal-Gomory closure of any compact convex set is a rational polytope. This resolves an open question of Schrijver (Ann Discret Math 9:291-296, 1980) for irrational polytopes, and generalizes the same result for the case of rational polytopes (Schrijver in Ann Discret Math 9:291-296, 1980), rational ellipsoids (Dey and Vielma in IPCO XIV, Lecture Notes in Computer Science, vol 6080. Springer, Berlin, pp 327-340, 2010) and strictly convex bodies (Dadush et al. in Math Oper Res 36:227-239, 2011).