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