Groupe d’études et de recherche en analyse des décisions

Conic representation of the convex hull of disjunctive sets and conic cuts for integer second order cone optimization

Julio C. Góez Lehigh University, États-Unis

We study the convex hull of the intersection between a convex set \(E\) (obtained by intersecting a convex cone with an affine set) and a linear disjunction. This intersection is at the core of solution techniques for Mixed Integer Conic Optimization. We prove that, if a cone \(K\) (resp. a cylinder \(C\)) exist that has the same intersection with the frontier of the disjunction as \(E\), then the convex hull is obtained by intersecting \(E\) with \(K\) (resp. \(C\)). The existence of such a cone or cylinder is difficult to prove for general conic optimization, but not for second order cones. We prove existence and unicity in this case, and provide a method for finding the cone (and hence the convex hull) for the continuous relaxation of the feasible set of a Mixed Integer Second Order Cone Optimization (MISOCO) problem, assumed to be an ellipsoid, intersected with a general linear disjunction. This cone provides a novel conic cut for MISOCO and we believe it can be used in branch-and-cut algorithms for MISOCO problems. This is joint work with Pietro Belotti, Imre Pólik, Ted K. Ralphs and Tamás Terlaky