School of Mathematics

Upcoming events

ERGO-Seminar: Akshay Gupte (UoE)

May 27th 15:10 - 16:00

Location: Microsoft Teams (contact Lars Schewe for details),

Description: Mixed-Integer Conic Optimization : Strong Duality, Extended Formulations, and Valid InequalitiesA mixed-integer conic problem (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}$), $K$ is a nonempty closed convex cone in E, and the partial order $u \\preceq_K v$ is defined as $v-u \\in K$. Commonly occurring special cases are with the orthant cone (MILP), Lorentz cone and positive semidefinite cone. A strong dual for MILP was established by Johnson (1973) and Jeroslow (1979), and this is an infinite-dimensional optimization problem in the space of subadditive functionals. Recently, Moran, Dey, Vielma (2012) extended this dual to MICP. These duals impose  subadditivity over the entire Euclidean space $E$ and have directional-derivative constraints for the continuous variables. We establish a new strong dual for MICP that has subadditivity constraints over only a restricted domain in E and has some linear and conic constraints instead of directional-derivatives. We also provide conditions for our dual to be a finite-dimensional conic program. As part of our proof, we extend the notion of packing sets from linear programs to conic programs. Using our strong dual, we construct an extended formulation for the mixed-integer hull of MICP. This generalizes the extension for linear IPs derived by Lasserre (2004,2005) using connections with integer Farkas lemma and subadditive duality. A projection cone-type result on the extended formulation yields a characterization of valid inequalities for the mixed-integer hull in the original space.We use tools from convex analysis, linear algebra, and theory of integer programming. The talk will only require some basic background in optimization.