Solving Mixed-Integer Nonlinear Programs by QP-Diving

TitleSolving Mixed-Integer Nonlinear Programs by QP-Diving
Publication TypeJournal Article
Year of Publication2012
AuthorsMahajan, A, Leyffer, S, Kirches, C
Date Published03/2012
Other NumbersANL/MCS-P2071-0312
Abstract

We present a new tree-search algorithm for solving mixed-integer nonlinear programs (MINLPs). Rather than relying on computationally expensive nonlinear solves at every node of the branch-and-bound tree, our algorithm solves a quadratic approximation at every node. We show that the resulting algorithm retains global convergence properties for convex MINLPs, and we present numerical results on a range of test problems. Our numerical experience shows that the new algorithm allows us to exploit warm-starting techniques from quadratic programming,resulting in a reduction in solve times for convex MINLPs by orders of magnitude on some classes of problems.

PDFhttp://www.mcs.anl.gov/papers/P2071-0312.pdf