Solving MINLPs with BARON Mustafa Kılınç & Nick Sahinidis Department of Chemical Engineering Carnegie Mellon University MINLP 2014 Carnegie Mellon University June 4, 2014 MIXED-INTEGER NONLINEAR PROGRAMS min f ( x, y) s.t. g( x, y)  0 n p x  R , y  Z • f, g are factorable functions that may be nonconvex. BOUNDING FACTORABLE PROGRAMS (Ryoo and Sahinidis, 1996; Similar to McCormick, 1976) Introduce variables for intermediate quantities whose envelopes are not known EXPLOITING CONVEXITY (Khajavirad and Sahinidis, 2014) Recognize convex subexpressions TIGHT RELAXATIONS f (x) f ( x) Concave Concave envelope over-estimator Convex Convex envelope under-estimator x x f (x) x Convex/concave envelopes often finitely generated (Tawarmalani and Sahinidis, 2001; Khajavirad and Sahinidis, 2013) POLYHEDRAL OUTER APPROXIMATION (Tawarmalani and Sahinidis, 2001, 2004) • Convex NLP solvers are not as robust as LP solvers • Linear programs can be solved efficiently • Outer-approximate convex relaxation by polyhedron BRANCH-AND-REDUCE Search Tree Discard Range Reduction Finiteness Partition x* Convexification 7 BRANCH-AND-REDUCE START Multistart search and reduction N Nodes? STOP Y Select Node Feasibility-based Preprocess reduction Lower Bound Y Delete Inferior? Node N Upper Bound Postprocess Optimality-based reduction Y Reduced? N Branch Branch-And-Reduce Optimization Navigator Components Subsolvers • Modeling language • NLP • Preprocessor • MINOS, SNOPT, CONOPT, IPOPT • I/O handler • LP • Range reduction • CPLEX, XPRESS, CLP • Interval arithmetic • Sparse matrix routines • Automatic differentiator Availability • Debugging facilities • Under GAMS and AIMMS • On NEOS server • Under MATLAB and YALMIP BARON HISTORY 1991-93 Duality-based range reduction Constraint propagation 1994-95 Branch-and-bound system Finite algorithm for separable concave minimization 1996-97 Parser for factorable programs; nonlinear relaxations Links to MINOS and OSL 1997-98 Polyhedral relaxations; Link to CPLEX Compressed data storage, tree traversal, … 2002 Under GAMS 2004 Branch-and-cut 2005-07 Local search; memory management, … 2009 Multi-term envelopes 2010-13 Multi-variate and multi-constraint envelopes/relaxations Links to CLP and IPOPT Hybrid LP/NLP relaxations 2014 Irreducible Inconsistent Set for infeasible problems Under MATLAB and YALMIP