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

2014/12/08 by Robert Hildebrand, Hildebrand, Robert, Timm Oertel +3
Mathematics · #FOS: Mathematics #Optimization and Control (math.OC) #math.OC

paper · pdf · doi:10.48550/arxiv.1412.2520

arxiv created 2015/03/10 · arxiv updated 2015/03/11

Abstract

We study the complexity of computing the mixed-integer hull conv(P∩ℤⁿ×ℝ^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=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.

Related

• A parameterized linear formulation of the integer hull
• Complexity of linear relaxations in integer programming
• Approximating mixed volumes to arbitrary accuracy
• Better Late than Never: the Complexity of Arrangements of Polyhedra
• The Triangle Closure is a Polyhedron