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