LaGO - a (heuristic) Branch and Cut algorithm for nonconvex MINLPs

Ivo Nowak, Stefan Vigerske

Preprint series: Institut für Mathematik, Humboldt-Universität zu Berlin (ISSN 0863-0976), 12

MSC 2000

90C26 Nonconvex programming

90C59 Approximation methods and heuristics

Abstract
We present a Branch and Cut algorithm of the software package LaGO to solve nonconvex mixed-integer nonlinear programs. A linear outer approximation is constructed from a convex relaxation of the problem. Since we do not require an algebraic representation of the problem, reformulation techniques for the construction of the convex relaxation cannot be applied, and we are restricted to sampling techniques in case of nonquadratic nonconvex functions. The linear relaxation is further improved by mixed-integer-rounding cuts. Also box reduction techniques are applied to improve efficiency. Numerical results on medium size testproblems and on the optimization of the design of an energy conversion system are presented to show the efficiency of the method.