Identifying and exploiting classes of nonconvex constraints whose feasible region is convex after branching can reduce the time to compute global solutions for nonlinear optimization problems. We develop techniques for identifying quadratic and nonlinear constraints whose feasible region can be represented as the union of a finite number of second-order cones, and we provide necessary and sufficient conditions for some reformulations. We then construct a library of small instances where these reformulations are applicable. Comparing our method to general-purpose solvers, we observe several orders of magnitude improvement in performance.
Citation
Technical Report ANL/MCS-P1801-1010, Argonne National Laboratory, October, 2010.