Effective separation of disjunctive cuts for convex mixed integer nonlinear programs

Abstract

We describe a computationally effective method for generating
\ndisjunctive inequalities for convex mixed-integer nonlinear programs
\n(MINLPs). The method relies on solving a sequence of cut-generating
\nlinear programs, and in the limit will generate an inequality as
\nstrong as can be produced by the cut-generating nonlinear program
\nsuggested by Stubbs and Mehrotra. Using this procedure, we are able
\nto approximately optimize over the rank one simple disjunctive closure
\nfor a wide range of convex MINLP instances. The results indicate that
\ndisjunctive inequalities have the potential to close a significant
\nportion of the integrality gap for convex MINLPs. In addition, we
\nfind that using this procedure within a branch-and-cut solver for
\nconvex MINLPs yields significant savings in total solution time for
\nmany instances. Overall, these results suggest that with an effective
\nseparation routine, like the one proposed here, disjunctive
\ninequalities may be as effective for solving convex MINLPs as they
\nhave been for solving mixed-integer linear programs.