Tutte seminar - Fatma Kilinc-Karzan

Friday, July 18, 2014 3:30 pm - 3:30 pm EDT (GMT -04:00)

Understanding Structure in Conic Mixed Integer Programs: From Minimal Inequalities to Conic Disjunctive Cuts

Speaker: Fatma Kilinc-Karzan
Affiliation: Carnegie Mellon University
Room: Mathematics 3 (M3) 3103


We study nonlinear mixed integer sets involving a general regular (closed, convex, full dimensional, and pointed) cone $K$ such as the nonnegative orthant, the Lorentz cone or the positive semidefinite cone, and introduce the class of $K$-minimal valid linear inequalities. Under mild assumptions, we show that these inequalities together with $x\in K$ constraint are sufficient to describe the convex hull. We relate $K$-minimal inequalities to  support functions of certain specific sets, and examine their properties via necessary, and sufficient conditions for an inequality to be $K$-minimal. This framework and the notion of $K$-minimality, naturally generalizes the corresponding results for Mixed Integer Linear Programs (MILPs), i.e., our results recover that the minimal inequalities for MILPs are generated by sublinear, piecewise linear functions. However, our study also reveals that such a cut generating function view is not possible for the conic case even when the cone involved is the Lorentz cone.