A common structure in convex mixed-integer nonlinear programs is additively separable nonlinear functions consisting of a sum of univariate functions. In the presence of such structures, we propose three improvements to the classical Outer Approximation algorithms that exploit separability. The first improvement is a simple extended formulation. The second a refined outer approximation. Finally, the third one is an Inner Approximation of the feasible region which approximates each univariate functions from the interior and can be used to find feasible solutions by solving mixed-integer linear programs. 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 applications.
Citation
Research Report, June 2011