Complexity of linear relaxations in integer programming

For a set X of integer points in a polyhedron, the smallest number of facets of any polyhedron whose set of integer points coincides with X is called the relaxation complexity rc(X). This parameter was introduced by Kaibel & Weltge (2015) and captures the complexity of linear descriptions of X without using auxiliary variables. Using tools from combinatorics, geometry of numbers, and quantifier elimination, we make progress on several open questions regarding rc(X) and its variant rcℚ(X), restricting the descriptions of X to rational polyhedra. As our main results we show that rc(X)=rcℚ(X) when: (a) X is at most four-dimensional, (b) X represents every residue class in (ℤ/2ℤ)d, (c) the convex hull of X contains an interior integer point, or (d) the lattice-width of X is above a certain threshold. Additionally, rc(X) can be algorithmically computed when X is at most three-dimensional, or X satisfies one of the conditions (b), (c), or (d) above. Moreover, we obtain an improved lower bound on rc(X) in terms of the dimension of X.