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. 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. Dorneich, M. C. and N. V. Sahinidis, Global optimization algorithms for chip layout and compaction, Engineering Optimization, 25:131-154, 1995.
  3. 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:797-818, 1996.
  4. Sahinidis, N. V., BARON: A general purpose global optimization software package, Journal of Global Optimization, 8:201-205, 1996.
  5. Ryoo, H. S. and N. V. Sahinidis, A branch-and-reduce approach to global optimization, Journal of Global Optimization,  8:107-139, 1996.
  6. Liu, M. L. and N. V. Sahinidis, Process planning in a fuzzy environment, European Journal of Operational Research, 100:142-169, 1997.
  7. Ghildyal, V., Design and development of a global optimization system, Master's thesis, Department of Mechanical & Industrial Engineering, University of Illinois, Urbana, IL, 1997.
  8. VanAntwerp, J. G., R. D. Braatz, and N. V. Sahinidis, Globally optimal robust control for systems with nonlinear time-varying perturbations, Computers & Chemical Engineering, 21:S125--S130, 1997.
  9. Shectman, J. P. and N. V. Sahinidis, A finite algorithm for global minimization of separable concave programs, Journal of Global Optimization, 12:1-36, 1998.
  10. Adhya, N., M. Tawarmalani, and N. V. Sahinidis, A Lagrangian approach to the pooling problem, Industrial & Engineering Chemistry Research, 38:1956-1972, 1999.
  11. Ryoo, H. S. and N. V. Sahinidis, Analysis of bounds for multilinear functions, Journal of Global Optimization, 19:403-424, 2001.
  12. M. Tawarmalani and N. V. Sahinidis, Semidefinite relaxations of fractional programs via novel convexification techniques, Journal of Global Optimization, 20:137-158, 2001.
  13. M. Tawarmalani and N. V. Sahinidis, Convex extensions and envelopes of lower semi-continuous functions, Mathematical Programming, 93:247-263, 2002.
  14. 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.
  15. Vaia, A. and N. V. Sahinidis, Simultaneous parameter estimation and model structure determination in FTIR spectroscopy by global MINLP optimization, Computers & Chemical Engineering, 27:763-779, 2003.
  16. Ryoo, H. S. and N. V. Sahinidis, Global optimization of multiplicative programs, Journal of Global Optimization, 26:387-418, 2003.
  17. Sahinidis, N. V., M. Tawarmalani, and M. Yu, Design of alternative refrigerants via global optimization, AIChE J., 49:1761-1775, 2003.
  18. Tawarmalani, M. and N. V. Sahinidis, Global optimization of mixed-integer nonlinear programs: A theoretical and computational study, Mathematical Programming, 99:563-591, 2004.
  19. Ahmed, S., M. Tawarmalani, and N. V. Sahinidis, A finite branch-and-bound algorithm for two-stage stochastic integer programming, Mathematical Programming, 100:355-377, 2004.
  20. 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.
  21. Tawarmalani, M. and N. V. Sahinidis, A polyhedral branch-and-cut approach to global optimization, Mathematical Programming, 103:225-249, 2005.
  22. Chang, Y. and N. V. Sahinidis, Global optimization in stabilizing controller design, Journal of Global Optimization, 38:509-526, 2007.
  23. 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.
  24. 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.
  25. 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.
  26. Rios, L. M. and N. V. Sahinidis, Portfolio optimization for wealth-dependent risk preferences, Annals of Operations Research, 177, 63-90, 2010.
  27. 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.
  28. Chang, Y. and N. V. Sahinidis, Steady-state process optimization with guaranteed robust stability under parametric uncertainty, AIChE Journal, 57:3395-3407, 2011.
  29. Khajavirad, A. and N. V. Sahinidis, Convex envelopes generated from finitely many compact convex sets, Mathematical Programming, 137:371-408, 2013.
  30. 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.
  31. 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.
  32. Samudra, A. and N. V. Sahinidis, Optimization-based framework for computer-aided molecular design, AIChE Journal, 59:3686-3701, 2013.
  33. Zorn, K. and N. V. Sahinidis, Global optimization of general nonconvex problems with intermediate bilinear substructures, Optimization Methods and Software, 29:442-462, 2013.
  34. Zorn, K. and N. V. Sahinidis, Computational experience with applications of bilinear cutting planes, Industrial & Engineering Chemistry Research, 52:7514-7525, 2013.
  35. Khajavirad, A., J. J. Michalek and N. V. Sahinidis, Relaxations of factorable functions with convex-transformable intermediates, Mathematical Programming, 144:107-140, 2014.
  36. Zorn, K. and N. V. Sahinidis, Global optimization of general nonconvex problems with intermediate polynomial substructures, Journal of Global Optimization, 59:673-693, 2014.
  37. Bao, X., A. Khajavirad, N. V. Sahinidis, and M. Tawarmalani, Global optimization of nonconvex problems with multilinear intermediates, Mathematical Programming Computation, 7:1-37, 2015.
  38. Puranik, Y. M. Kilinc, N. V. Sahinidis, T. Li, A. Gopalakrishnan, B. Besancon, and Th. Roba, Global optimization of an industrial gas network operation, AIChE Journal, 62:3215-3224, 2016.
  39. Puranik, Y. and N. V. Sahinidis, Domain reduction techniques for global NLP and MINLP optimization, Constraints, 22:338-376, 2017.
  40. Puranik, Y. and N. V. Sahinidis, Bounds tightening based on optimality conditions for nonconvex box-constrained optimization, Journal of Global Optimization, 67:59-77, 2017.
  41. Puranik, Y. and N. V. Sahinidis, Deletion presolve for accelerating infeasibility diagnosis in optimization models, INFORMS Journal on Computing, 29:754-766, 2017.