Strengthening the Sequential Convex MINLP Technique by Perspective Reformulations

The Sequential Convex MINLP (SC-MINLP) technique is a solution method for NonConvex Mixed-Integer NonLinear Problems where the nonconvexities are separable. It is based on solving a sequence of Convex MINLPs which trade a better and better relaxation of the nonlinear nonconvex part of the problem with the introduction of more and more piecewise-linear nonconvex terms, and therefore binary variables. The Convex MINLPs are obtained by separately considering each separable nonconvex term in the intervals in which it is convex and those in which it is concave, where the former are left in their original form while the latter are piecewise-linearized. Because each interval corresponds to a semi-continuous variable, we rather propose to modify the convex terms using the Perspective Reformulation technique to strengthen the bounds. We show by means of experimental results on different classes of instances that doing so significantly decreases the solution time of the Convex MINLPs, which is the most time consuming part of the approach, and has therefore the potential to improving the overall effectiveness of SC-MINLP.