Global Optimization

A plethora of problems in process synthesis, design, manufacturing, and the chemical and biological sciences require the solution of nonlinear optimization problems with multiple local solutions.

Our work in this area aims at developing an all-purpose, rigorous global optimization methodology for continuous, integer, and mixed integer nonlinear programs. Our recent results have included the development of: (a) a unifying framework for domain reduction which produces existing and new range-reduction techniques for integer and nonlinear programs, (b) a theory of convex extensions, which we employ to develop convex/concave envelopes of a variety of nonlinear functions, leading to the first semidefinite programming relaxation for fractional programs, (c) an entirely linear outer-approximation scheme for factorable nonlinear programs, (d) finite branching schemes for certain continuous nonconvex problem classes for which standard branch and bound approaches are merely convergent.

Applications of our algorithms have included molecular design, chemical process design, long range planning of chemical processes, chip layout and compaction, design of just-in-time manufacturing systems, and control of complex chemical processes. Problems which up to recent times were thought to require advanced (such as parallel or distributed) computers for their solution, can be solved with modest hardware using our global optimization package BARON. This software has served as an enabling technology in a variety of application areas, including:

• modeling and design of metabolic pathways (S. Ghosh, T. Zhu, I. E. Grossmann, M. M. Ataai, and M. M. Domach, Metabolic Engineering, 8, 491-507, 2006),
• the development of new Runge-Kutta methods for partial differential equations (S. J. Ruuth, Mathematics of Computation, 75, 183-207, 2006),
• equilibrium computations and mechanism design (M. Ferris, S. P. Dirkse, and A. Meeraus, Frontiers in Applied General Equilibrium Modeling, 2005),
• energy policy making (A. S. Manne and L. Barreto, Energy Economics, 26, 621-633, 2004),
• agricultural advisory services (S. M. Cabrini, B. G. Stark, H. Onal, S. H. Irwin, D. L. Good and J. Martinez-Filho, Manufacturing & Service Operations Management, 6, 237-252, 2004), and
• process estimation for control (J. Roll, A. Bemporand, and L. Ljung, Automatica, 40, 37-50, 2004).

Currently, our efforts center around further advancing the state of the art of global optimization algorithms and offering solutions to important applications, including molecular design and analysis. The ultimate goal is to provide, through BARON, a precise and valuable computational tool to engineers and scientists.

Selected Publications:

1. Chang, Y. and N. V. Sahinidis, Global optimization in stabilizing controller design, Journal of Global Optimization, 38(4), 509-526, 2007.
2. Tawarmalani, M. and N. V. Sahinidis, A polyhedral branch-and-cut approach to global optimization, Mathematical Programming, Ser. B, 103, 225-249, 2005.
3. Sahinidis, N. V. and M. Tawarmalani, Accelerating branch-and-bound through a modeling language construct for relaxation-specific constraints, Journal of Global Optimization, 32, 259-280, 2005.
4. Ahmed, S., M. Tawarmalani, and N. V. Sahinidis, A finite branch-and-bound algorithm for two-stage stochastic integer programming, Mathematical Programming, 100(2), 355-377, 2004.
5. Tawarmalani, M. and N. V. Sahinidis, Global optimization of mixed-integer nonlinear programs: A theoretical and computational study, Mathematical Programming, 99(3), 563-591, 2004.
6. Sahinidis, N. V., M. Tawarmalani, and M. Yu, Design of alternative refrigerants via global optimization, AIChE J., 49(7), 1761-1775, 2003.
7. Ryoo, H. S. and N. V. Sahinidis, Global optimization of multiplicative programs, Journal of Global Optimization, 26(4), 387-418, 2003.
8. Vaia, A. and N. V. Sahinidis, Simultaneous parameter estimation and model structure determination in FTIR spectroscopy by global MINLP optimization, Computers & Chemical Engineering, 27(6), 763-779, 2003.
9. Tawarmalani, M. and N. V. Sahinidis, Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications, 504 pages, Kluwer Academic Publishers, Dordrecht, Vol. 65 in "Nonconvex Optimization And Its Applications" series, 2002. Ordering information.
10. M. Tawarmalani and N. V. Sahinidis, Convex extensions and envelopes of lower semi-continuous functions, Mathematical Programming, 93(2), 247-263, 2002.
11. M. Tawarmalani and N. V. Sahinidis, Semidefinite relaxations of fractional programs via novel convexification techniques, Journal of Global Optimization, 20(2), 137-158, 2001.
12. Ryoo, H. S. and N. V. Sahinidis, Analysis of bounds for multilinear functions, Journal of Global Optimization, 19(4), 403-424, 2001.
13. Adhya, N., M. Tawarmalani, and N. V. Sahinidis, A Lagrangian approach to the pooling problem, Industrial & Engineering Chemistry Research, 38(5), 1956-1972, 1999.
14. Shectman, J. P. and N. V. Sahinidis, A finite algorithm for global minimization of separable concave programs, Journal of Global Optimization, 12(1), 1-36, 1998.
15. Liu, M. L. and N. V. Sahinidis, Process planning in a fuzzy environment, European Journal of Operational Research, 100(1), 142-169, 1997
16. Ryoo, H. S. and N. V. Sahinidis, A branch-and-reduce approach to global optimization, Journal of Global Optimization,  8(2), 107-139, 1996.
17. Sahinidis, N. V., BARON: A general purpose global optimization software package, Journal of Global Optimization, 8(2), 201-205, 1996.
18. Gutierrez, R. A. and N. V. Sahinidis, A branch-and-bound approach for machine selection in just-in-time manufacturing systems, International Journal of Production Research, 34(3), 797-818, 1996.
19. Dorneich, M. C. and N. V. Sahinidis, Global optimization algorithms for chip layout and compaction, Engineering Optimization, 25(2), 131-154, 1995.
20. Ryoo, H. S. and N. V. Sahinidis, Global optimization of nonconvex NLPs and MINLPs with applications in process design, Computers & Chemical Engineering, 19(5), 551-566, 1995.