Solving Mixed-Integer Nonlinear Programs by QP-Diving
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.
Keywords: Mixed-Integer Nonlinear Programming, Sequential Quadratic Programming, Branch-and-Bound
Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )
Category 2: Nonlinear Optimization (Quadratic Programming )
Citation: Technical Report ANL/MCS-P2071-0312, Argonne National Laboratory, March, 2012.
Entry Submitted: 03/26/2012
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|