386667 Global Optimization of Mixed-Integer Nonlinear Optimization Problems

Wednesday, November 19, 2014: 12:30 PM
406 - 407 (Hilton Atlanta)
Nick Sahinidis, Chemical Engineering, Carnegie Mellon University, Pittsburgh, PA and Mustafa Kilinc, Carnegie Mellon University, PIttsburgh, PA

The development of the branch-and-reduce approach to global optimization in the past emphasized constraint propagation and convexification techniques that aimed to provide tight relaxations for continuous optimization problems and relaxations of integer programs [1, 2, 3, 4]. We report recent developments in the integer arsenal of branch-and-reduce and their implementation in the global optimization software BARON. New features include integrality-based techniques, such as automatic constraint classification, preprocessing, probing, active constraint management, branching, and node selection rules. Specific cutting plane generation now produces knapsack cuts, GUB cuts, clique cuts, implication cuts, and flow cuts. Finally, mixed-integer linear programming relaxations are solved to construct new feasible solutions and improve relaxations at nodes of the search tree. Extensive computational results will be presented on problems from a collection of test sets, including process synthesis and operations problems from minlp.org.

1. Ryoo, H. S. and N. V. Sahinidis, Global optimization of nonconvex NLPs and MINLPs with applications in process design, Computers & Chemical Engineering, 19, 551-566, 1995.
2. Sahinidis, N. V., Global optimization and constraint satisfaction: The branch-and-reduce approach, pp. 1-16 in C. Bliek, C. Jermann, and A. Neumaier (eds.), Global Optimization and Constraint Satisfaction, Lecture Notes in Computer Science, Vol. 2861, Springer, Berlin, 2003.
3. Tawarmalani, M. and N. V. Sahinidis, Global optimization of mixed-integer nonlinear programs: A theoretical and computational study, Mathematical Programming, Ser. A, 99, 563-591, 2004.
4. Bao, X., A. Khajavirad, N. V. Sahinidis, and M. Tawarmalani, Global optimization of nonconvex problems with multilinear intermediates, Mathematical Programming Computation, DOI: 10.1007/s12532-014-0073-z, 2015.

Extended Abstract: File Not Uploaded
See more of this Session: Advances in Optimization II
See more of this Group/Topical: Computing and Systems Technology Division