For a finite set $X \subset \Z^d$ that can be represented as $X = Q \cap \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) \leq d$ for every $d \geq 5$. That is, since $\rc_\Q(\Delta_d)=d+1$, irrationality can reduce the minimal size of relaxations. This answers an open question posed by Kaibel and Weltge (Lower bounds on the size of integer programs without additional variables, \emph{Mathematical Programming}, 154(1):407--425, 2015). Moreover, we prove the asymptotic statement $\rc(\Delta_d) \in O(\frac{d}{\sqrt{\log(d)}})$, which shows that the ratio $\rc(\Delta_d)/\rc_\Q(\Delta_d)$ goes to $0$, as $d\to \infty$.
Article
View The role of rationality in integer-programming relaxations