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 its relaxation complexity rc(X). This parameter has been 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_Q(X), restricting the descriptions of X to rational polyhedra. As our main results we show that rc(X) = rc_Q(X) when: (a) X is at most four-dimensional, (b) X represents every residue class in (Z/2Z)^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 when X satisfies one of the conditions (b), (c), or (d) above.
In the talk I will focus on the main ideas and the occuring phenomena that separate small from large dimensions.
This is joint work with Gennadiy Averkov (https://arxiv.org/abs/2003.07817).