The role of rationality in integer-programming relaxations

For a finite set X⊂Zd that can be represented as X=Q∩Zd 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 rcQ(X) restricts the definition of rc(X) to rational polyhedra Q. In this article, we focus on X=Δd, the vertex set of the standard simplex, which consists of the null vector and the standard unit vectors in Rd. We show that rc(Δd)≤d for every d≥5. That is, since rcQ(Δ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(Δd)∈O(dlog(d)√/), which shows that the ratio rc(Δd)rcQ(Δd)/ goes to 0, as d→∞.