Closedness of integer hulls of simple conic sets

Diego A. Moránr, Santanu S. Dey

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

Let C be a full-dimensional pointed closed convex cone in Rm obtained by taking the conic hull of a strictly convex set. Given A ∈ Qm×n1, B ∈ Qm×n2, and b ∈ Qm, a simple conic mixed-integer set (SCMIS) is a set of the form {(x, y) ∈ Zn1 × Rn2 | Ax + By -b ∈ C}. In this paper, we give a complete characterization of the closedness of convex hulls of SCMISs. Under certain technical conditions on the cone C, we show that the closedness characterization can be used to construct a polynomial-time algorithm to check the closedness of convex hulls of SCMISs. Moreover, we also show that the Lorentz cone satisfies these technical conditions. In the special case of pure integer problems, we present sufficient conditions, which can be checked in polynomial time, to verify the closedness of intersection of SCMISs.

Original languageEnglish
Pages (from-to)70-99
Number of pages30
JournalSIAM Journal on Discrete Mathematics
Volume30
Issue number1
DOIs
StatePublished - 2016
Externally publishedYes

Keywords

  • Closedness
  • Mixed-integer convex programming
  • Polynomial-time algorithm

Fingerprint

Dive into the research topics of 'Closedness of integer hulls of simple conic sets'. Together they form a unique fingerprint.

Cite this