Non-Convex Mixed-Integer Nonlinear Programming: A Survey

A wide range of problems arising in practical applications can be formulated as Mixed-Integer Non-Linear Programs (MINLPs). For the case in which the objective and constraint functions are convex, some quite effective exact and heuristic algorithms are available. When non-convexities are present, however, things become much more difficult, since then even the continuous relaxation is a global optimisation problem. The authors survey the literature on non-convex MINLP, discussing applications, algorithms and software. Special attention is paid to the case in which the objective and constraint functions are quadratic.