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 rc Q(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 rc Q(Δ 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→ ∞ .