Claudia D’Ambrosio, CNRS and Ecole Polytechnique

Abstract

In this talk, we focus on mixed integer non linear programming (MINLP) problems with non convexities that can be formulated as sums of univariate functions. D'Ambrosio et al. 2009 and D'Ambrosio et al. 2012 proposed a method called Sequential Convex MINLP (SC-MINLP), an iterative algorithm based on lower and upper bounds obtained by solving a convex MINLP and a non convex non linear program, respectively. The method aims at finding a global solution of the tackled MINLP and exploits the fact that the convex or concave parts of univariate functions can be identified numerically. The weaknesses of the original version of the SC-MINLP method are mainly two: on the one hand, solving several (one per iteration) convex MINLPs is time-consuming; on the other hand, at each iteration, the convex MINLP is modified to improve the lower bound and no information about the previous convex MINLP and its optimal solution is exploited. These two weaknesses are addressed in two recent works: in the first, a strengthening of the convex MINLP relaxation is proposed based on perspective reformulation. In the second, a disjunctive programming approach was explored to better approximate the concave parts of each univariate function. Extensive computational experiments show a significant speedup of the original SC-MINLP method.