Optimization Online


Solving Mixed-Integer Nonlinear Programs by QP-Diving

Ashutosh Mahajan(mahajan***at***mcs.anl.gov)
Sven Leyffer(leyffer***at***mcs.anl.gov)
Christian Kirches(christian.kirches***at***iwr.uni-heidelberg.de)

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.

Download: [PDF]

Entry Submitted: 03/26/2012
Entry Accepted: 03/27/2012
Entry Last Modified: 03/26/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society