The role of rationality in integer-programming relaxations

• 成果类型: Article
• 署名作者: Aprile, Manuel; Averkov, Gennadiy; Di Summa, Marco; Hojny, Christopher
• 署名单位: University of Padua; Brandenburg University of Technology Cottbus; Eindhoven University of Technology
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-023-01994-w
• 发表日期: 2024
• 页码: 745-771

摘要

For a finite set X subset of Z(d) that can be represented as X = Q n Z(d) for some polyhedron Q, we call Q a relaxation of X and define the relaxation complexity rc(X) of X as the least number of facets among all possible relaxations Q of X. The rational relaxation complexity rc(Q)( X) restricts the definition of rc( X) to rational polyhedra Q. In this article, we focus on X = Delta(d), the vertex set of the standard simplex, which consists of the null vector and the standard unit vectors in R-d. We show that rc(Delta(d)) = d for every d >= 5. That is, since rcQ(Delta(d)) = d + 1, irrationality can reduce the minimal size of relaxations. This answers an open question posed by Kaibel and Weltge (Math Program 154(1):407-425, 2015). Moreover, we prove the asymptotic statement rc(Delta(d))epsilon O(d/root log(d)), which shows that the ratio rc(Delta(d))/rc(Q)(Delta d) goes to 0, as d ->infinity.