Optimization Online


Closedness of Integer Hulls of Simple Conic Sets

Diego Moran (dmoran***at***gatech.edu)
Santanu S. Dey (santanu.dey***at***isye.gatech.edu)

Abstract: Let $C$ be a full-dimensional pointed closed convex cone in $R^m$ obtained by taking the conic hull of a strictly convex set. Given $A \in Q^{m \times n_1}$, $B \in Q^{m \times n_2}$ and $b \in Q^m$, a simple conic mixed-integer set (SCMIS) is a set of the form $\{(x,y)\in Z^{n_1} \times R^{n_2}\,|\,\ Ax +By -b \in 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, that can be checked in polynomial-time, to verify the closedness of intersection of SCMISs.

Keywords: Closedness, Polynomial-time algorithm, Mixed-integer convex programming

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )


Download: [PDF]

Entry Submitted: 06/07/2013
Entry Accepted: 06/07/2013
Entry Last Modified: 06/07/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society