Akshay Gupte, Clemson University

Abstract

A mixed-integer conic program (MICP) optimizes a linear function over the set of mixed-integer points in the nonnegative orthant satisfying the conic inequality constraints $A(x) preceq_K b$, where $A: R^n to E$ is a linear map, E is a  Euclidean space (either $R^m$ or $R^{mtimes m}$), and $K$ is a nonempty closed convex pointed full-dimensional cone. Commonly occurring special cases are MILP, MISOCP, and MISDP. Strong duals for MILPs were established in the 1970’s and these duals are infinite-dimensional optimization problems in the space of subadditive functionals. More recently, Moran, Dey, and Vielma (2012) generalized these results to MICP and established strong duality under some technical conditions. This dual imposes subadditivity over the domain of the functionals, which is taken to be the entire space $E$. Our first main result is to show that strong duality persists even if the domain of the functional is any set that is closed under sum decomposition over the polyhedral cone formed by the generators of $A$. This reduces the size of the subadditive dual and in particular, our dual is an LP when the primal is pure integer, which is a generalization of classical results on linear IPs. Our second result is to establish a new strong dual for MICP that has subadditivity constraints and some other linear and conic constraints. Thus, it dispenses with the directional-derivative constraints that the Moran et al. dual has for continuous variables and which are computationally intractable. Our third result is to use our strong duals to construct extended formulations for the integer hull of MICP. This  generalizes the extension for linear IPs that was derived by Lasserre (2004,2005) using connections with integer Farkas lemma and subadditive duality.

This is based on joint work with Temitayo Ajayi and Andrew Schaefer (Rice University) and Amin Khademi (Clemson University).