An Outer-Inner Approximation for separable MINLPs

A common structure in convex mixed-integer nonlinear programs is separable nonlinear functions. In the presence of such structures, we propose three improvements to the outer approximation algorithms. The first improvement is a simple extended formulation, the second is a refined outer approximation, and the third is a heuristic inner approximation of the feasible region. These methods have been implemented in the open source solver Bonmin and are available for download from the COIN-OR project website. We test the effectiveness of the approach on three real-world applications and on a larger set of models from an MINLP benchmark library. Finally, we show how the techniques can be extended to perspective formulations of several problems. The proposed tools lead to an important reduction in average computing time on most tested instances.


LIX, Ecole Polytechnique, F-91128 Palaiseau, France 06/2012



View An Outer-Inner Approximation for separable MINLPs