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 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, (e) convex and concave envelopes for a variety of frequently occurring functions.

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, design and analysis of metabolic and other biological 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 supply chain operations optimization and 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. Khajavirad, A., J. J. Michalek and N. V. Sahinidis, Relaxations of factorable functions with convex-transformable intermediates, submitted for publication.
  2. Zorn, K. and N. V. Sahinidis, Global optimization of general nonconvex problems with intermediate bilinear substructures, submitted for publication, 2012.
  3. Samudra, A. and N. V. Sahinidis, Optimization-based framework for computer-aided molecular design, submitted for publication, 2012.
  4. Amaran, S. and N. V. Sahinidis, Global optimization of nonlinear least-squares problems by branch-and-bound and optimality constraints, Top, 20, 154–172, 2012.
  5. Khajavirad, A. and N. V. Sahinidis, Convex envelopes of products of convex and component-wise concave functions, Journal of Global Optimization, 52, 391-409, 2012.
  6. Khajavirad, A. and N. V. Sahinidis, Convex envelopes generated from finitely many compact convex sets, Mathematical Programming, DOI 10.1007/s10107-011-0496-5, 2011.
  7. Chang, Y. and N. V. Sahinidis, Steady-state process optimization with guaranteed robust stability under parametric uncertainty, AIChE Journal, 57, 3395-3407, 2011.
  8. Bao, X., N. V. Sahinidis and M. Tawarmalani, Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons, Mathematical Programming, 129:129-157, 2011.
  9. Rios, L. M. and N. V. Sahinidis, Portfolio optimization for wealth-dependent risk preferences, Annals of Operations Research, 177, 63-90, 2010.
  10. Bao, X. and N. V. Sahinidis, Finite algorithms for global minimization of separable concave programs, in T. Coleman and P. Pardalos (eds.), Workshop on Global Optimization, Fields Institute Communications, Vol. 55, American Mathematical Society, pp. 17-30, 2009.
  11. Samudra, A. and N. V. Sahinidis, Design of secondary refrigerants: A combined optimization-enumeration approach, in M. M. El-Halwagi and A. A. Linninger (eds.): Proceedings of the 7th International Conference on the Foundations of Computer-Aided Process Design, CRC Press, pp. 879-886, 2009.
  12. Bao, X., N. V. Sahinidis, and M. Tawarmalani, Multiterm polyhedral relaxations for nonconvex, quadratically-constrained quadratic programs, Optimization Methods and Software, 24, 485-504, 2009.
  13. Chang, Y. and N. V. Sahinidis, Global optimization in stabilizing controller design, Journal of Global Optimization, 38(4), 509-526, 2007.
  14. Tawarmalani, M. and N. V. Sahinidis, A polyhedral branch-and-cut approach to global optimization, Mathematical Programming, Ser. B, 103, 225-249, 2005.
  15. 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.
  16. 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.
  17. 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.
  18. Sahinidis, N. V., M. Tawarmalani, and M. Yu, Design of alternative refrigerants via global optimization, AIChE J., 49(7), 1761-1775, 2003.
  19. Ryoo, H. S. and N. V. Sahinidis, Global optimization of multiplicative programs, Journal of Global Optimization, 26(4), 387-418, 2003.
  20. 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.
  21. 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. Compare prices at addall.com
  22. M. Tawarmalani and N. V. Sahinidis, Convex extensions and envelopes of lower semi-continuous functions, Mathematical Programming, 93(2), 247-263, 2002.
  23. M. Tawarmalani and N. V. Sahinidis, Semidefinite relaxations of fractional programs via novel convexification techniques, Journal of Global Optimization, 20(2), 137-158, 2001.
  24. Ryoo, H. S. and N. V. Sahinidis, Analysis of bounds for multilinear functions, Journal of Global Optimization, 19(4), 403-424, 2001.
  25. Adhya, N., M. Tawarmalani, and N. V. Sahinidis, A Lagrangian approach to the pooling problem, Industrial & Engineering Chemistry Research, 38(5), 1956-1972, 1999.
  26. 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.
  27. Liu, M. L. and N. V. Sahinidis, Process planning in a fuzzy environment, European Journal of Operational Research, 100(1), 142-169, 1997
  28. Ryoo, H. S. and N. V. Sahinidis, A branch-and-reduce approach to global optimization, Journal of Global Optimization,  8(2), 107-139, 1996.
  29. Sahinidis, N. V., BARON: A general purpose global optimization software package, Journal of Global Optimization, 8(2), 201-205, 1996.
  30. 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.
  31. Dorneich, M. C. and N. V. Sahinidis, Global optimization algorithms for chip layout and compaction, Engineering Optimization, 25(2), 131-154, 1995.
  32. 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.