Paper detail

The role of rationality in integer-programming relaxations

For a finite set $X \subset \mathbb{Z}^d$ that can be represented as $X = Q \cap \mathbb{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_\mathbb{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 $\mathbb{R}^d$. We show that $rc(Δ_d) \leq d$ for every $d \geq 5$. That is, since $rc_{\mathbb{Q}}(Δ_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, Mathematical Programming, 154(1):407-425, 2015). Moreover, we prove the asymptotic statement $rc(Δ_d) \in O(\frac{d}{\sqrt{\log(d)}})$, which shows that the ratio $rc(Δ_d)/rc_{\mathbb{Q}}(Δ_d)$ goes to $0$, as $d\to \infty$.