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

Hildebrand, Robert, Oertel, Timm ORCID: https://orcid.org/0000-0001-5720-8978 and Weismantel, Robert 2015. Note on the complexity of the mixed-integer hull of a polyhedron. Operations Research Letters 43 (3) , pp. 279-282. 10.1016/j.orl.2015.03.002

Preview

PDF - Accepted Post-Print Version Download (901kB) | Preview

Abstract

We study the complexity of computing the mixed-integer hull View the MathML source 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 View the MathML source in polynomial time and give bounds on the number of vertices of the mixed-integer hull. Keywords

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Mathematics
Subjects:	Q Science > QA Mathematics
Publisher:	Elsevier
ISSN:	0167-6377
Date of First Compliant Deposit:	30 March 2016
Date of Acceptance:	3 March 2015
Last Modified:	03 Dec 2024 10:30
URI:	https://orca.cardiff.ac.uk/id/eprint/86768

Citation Data

Cited 6 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item