Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

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

[thumbnail of mixed-integer-hull.pdf]
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: 06 Nov 2023 20:14
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 Edit Item

Downloads

Downloads per month over past year

View more statistics