Understanding Structure in Conic Mixed Integer Programs: From Minimal Inequalities to Conic Disjunctive Cuts
|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.
200 University Avenue West
Waterloo, ON N2L 3G1