Note on the complexity of the mixed-integer hull of a polyhedron - Hildebrand, Robert; Oertel, Timm; Weismantel, Robert (Operations Research Letters, 2015)
We study the complexity of computing the mixed-integer hull conv(P∩(Zn×Rd)) 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 a finite set V⊂Qn+d, with n fixed, we compute a vertex description of the mixed-integer hull of conv(V) in polynomial time and give bounds on the number of vertices of the mixed-integer hull.
CRIS-Team Scopus Importer:2021-09-09
Keywords: Mixed-integer concave minimization; Mixed-integer hull; Polyhedron