Mixed Integer Second Order Cone Optimization, Disjunctive Conic Cuts: Theory and experiments

Mixed Integer Second Order Cone Optimization (MISOCO) problems allow practitioners to mathematically describe a wide variety of real world engineering problems including supply chain, finance, and networks design. A MISOCO problem minimizes a linear function over the set of solutions of a system of linear equations and the Cartesian product of second order cones of various dimensions, where a subset of the variables is constrained to be integer. This thesis presents a technique to derive inequalities that help to obtain a tighter mathematical description of the feasible set of a MISOCO problem. This improved description of the problem usually leads to accelerate the process of finding its optimal solution. In this work we extend the ideas of disjunctive programming, originally developed for mixed integer linear optimization, to the case of MISOCO problems. The extension presented here results in the derivation of a novel methodology that we call \emph{disjunctive conic cuts} for MISOCO problems. The analysis developed in this thesis is separated in three parts. In the first part, we introduce the formal definition of disjunctive conic cuts. Additionally, we show that under some mild assumptions there is a necessary and sufficient condition that helps to identify a disjunctive conic cut for a given convex set. The main appeal of this condition is that it can be easily verified in the case of MISOCO problems. In the second part, we study the geometry of sets defined by a single quadratic inequality. We show that for some of these sets it is possible to derive a close form to build a disjunctive conic cut. In the third part, we show that the feasible set of a MISOCO problem with a single cone can be characterized using sets that are defined by a single quadratic inequality. Then, we present the results that provide the criteria for the derivation of disjunctive conic cuts for MISOCO problems. Preliminary numerical experiments with our disjunctive conic cuts used in a branch-and-cut framework provide encouraging results where this novel methodology helped to solve MISOCO problems more efficiently. We close our discussion in this thesis providing some highlights about the questions that we consider worth pursuing for future research