%0 Journal Article
%T Note on the Complexity of the Mixed-Integer Hull of a Polyhedron
%A Robert Hildebrand
%A Timm Oertel
%A Robert Weismantel
%J Mathematics
%D 2014
%I arXiv
%X We study the complexity of computing the mixed-integer hull $\operatorname{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=\operatorname{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.
%U http://arxiv.org/abs/1412.2520v2