Complexity of linear relaxations in integer programming
Gennadiy Averkov, Matthias Schymura · Mathematical Programming · 2021
Abstract 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 $${{\,\mathrm{rc}\,}}(X)$$ rc ( X ) . This parameter, introduced by Kaibel & Weltge (2015), 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 $${{\,\mathrm{rc}\,}}(X)$$ rc ( X ) and its variant $${{\,\mathrm{rc}\,}}_\mathbb {Q}(X)$$ rc Q ( X ) , restricting the descriptions of X to rational polyhedra. As our main results we show that $${{\,\mathrm{rc}\,}}(X) = {{\,\mathrm{rc}\,}}_\mathbb {Q}(X)$$ rc ( X ) = rc Q ( X ) when: (a) X is at most four-dimensional, (b) X represents every residue class in $$(\mathbb {Z}/2\mathbb {Z})^d$$ ( Z / 2 Z ) 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, $${{\,\mathrm{rc}\,}}(X)$$ 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 $${{\,\mathrm{rc}\,}}(X)$$ rc ( X ) in terms of the dimension of X.