Note on the complexity of the mixed-integer hull of a polyhedron

Hildebrand R, Oertel T, Weismantel R (2015)

Publication Type: Journal article

Publication year: 2015

Journal

Operations Research Letters Elsevier

Book Volume: 43

Pages Range: 279-282

Journal Issue: 3

DOI: 10.1016/j.orl.2015.03.002

Abstract

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.

Authors with CRIS profile

Timm Oertel

Additional Organisation(s)

Professur für Mathematische Analyse von Daten (Data Analytics)

Involved external institutions

Eidgenössische Technische Hochschule Zürich (ETHZ) / Swiss Federal Institute of Technology in Zurich CH Switzerland (CH)

How to cite

APA:

Hildebrand, R., Oertel, T., & Weismantel, R. (2015). Note on the complexity of the mixed-integer hull of a polyhedron. Operations Research Letters, 43(3), 279-282. https://dx.doi.org/10.1016/j.orl.2015.03.002

MLA:

Hildebrand, Robert, Timm Oertel, and Robert Weismantel. "Note on the complexity of the mixed-integer hull of a polyhedron." Operations Research Letters 43.3 (2015): 279-282.

BibTeX: Download