Note on the Complexity of the Mixed-Integer Hull of a Polyhedron

Abstract

We study the complexity of computing the mixed-integer hull $\mathrm{conv}(P\cap {\mathbb{Z}}^n\times {\mathbb{R}}^d)$ of a polyhedron $P$. Given an inequality description, with one integer variable, the mixed-integer hull can have exponentially many vertices and facets in $d$. For $n,d$ fixed, we give an algorithm to find the mixed integer hull in polynomial time. Given $P=\mathrm{conv}(V)$ and $n$ fixed, we compute a vertex description of the mixed-integer hull in polynomial time and give bounds on the number of vertices of the mixed integer hull.

References in corpus (1)

• On the number of vertices in integer linear programming problems