Skip to main content
SpringerLink
Log in

Scatter search for chemical and bio-process optimization

  • Original Paper
  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

Scatter search is a population-based method that has recently been shown to yield promising outcomes for solving combinatorial and nonlinear optimization problems. Based on formulations originally proposed in 1960s for combining decision rules and problem constraints such as the surrogate constraint method, scatter search uses strategies for combining solution vectors that have proved effective in a variety of problem settings. In this paper, we develop a general purpose heuristic for a class of nonlinear optimization problems. The procedure is based on the scatter search methodology and treats the objective function evaluation as a black box, making the search algorithm context-independent. Most optimization problems in the chemical and bio-chemical industries are highly nonlinear in either the objective function or the constraints. Moreover, they usually present differential-algebraic systems of constraints. In this type of problem, the evaluation of a solution or even the feasibility test of a set of values for the decision variables is a time-consuming operation. In this context, the solution method is limited to a reduced number of solution examinations. We have implemented a scatter search procedure in Matlab (Mathworks, 2004) for this special class of difficult optimization problems. Our development goes beyond a simple exercise of applying scatter search to this class of problems, but presents innovative mechanisms to obtain a good balance between intensification and diversification in a short-term search horizon. Computational comparisons with other recent methods over a set of benchmark problems favor the proposed procedure.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Abramson, M.A.: Pattern search algorithms for mixed variable general constrained optimization problems. PhD Thesis, Rice University (2002)

  2. Bailey J.E. (1998) Mathematical modeling and analysis in biochemical engineering: past accomplishments and future opportunities. Biotechnol. Progr. 14, 8-20

    Article  Google Scholar 

  3. Banga J.R., Balsa-Canto E., Moles C.G., Alonso A.A. (2003a). Improving food processing using modern optimization methods. Trends Food Sci Technol. 14, 131-144

    Article  Google Scholar 

  4. Banga J.R., Moles C.G., Alonso A.A. (2003b). Global optimization of bioprocesses using stochastic and hybrid methods. In: Floudas C.A., Pardalos P.M. (eds.) Frontiers In Global Optimization. Nonconvex Optimization and Its Applications, vol. 74. Kluwer Academic Publishers, Hingham, MA, USA, pp 45-70

    Google Scholar 

  5. Biegler L.T., Grossmann I.E. (2004). Retrospective on optimization. Comput. Chem. Eng. 28(8): 1169-1192

    Google Scholar 

  6. Boender C.G.E., Rinooy Kan A.H.G., Timmer G.T., Stougie L. (1982). A stochastic method for global optimization. Math. Program. 22, 125-140

    Article  Google Scholar 

  7. Box G.E.P., Hunter W.G., MacGregor J.F., Erjavec J. (1973). Some problems associated with the analysis of multiresponse data. Technometrics. 15, 33-51

    Article  Google Scholar 

  8. Csendes T. (1988). Nonlinear parameter estimation by global optimization–efficiency and reliability. Acta Cybernet. 8(4): 361-370

    Google Scholar 

  9. Dennis J.E., Gay D.M., Welsch R.E. (1981). Algorithm 573: NL2SOL–An adaptive nonlinear least-squares algorithm. Acm. Trans. Math. Soft. 7, 369-383

    Article  Google Scholar 

  10. Dolan, E.D., Moré, J.J., Munson, T.S.: Benchmarking optimization problems with COPS 3.0. Technical Report ANL/MCS-TM-273, Argonne National Laboratory (2004)

  11. Finkel, D.E., Kelley, C.T.: An Adaptive Restart Implementation of DIRECT. Technical Report CRSC-TR04–30, NC State University (2004)

  12. Floudas C.A., Akrotirianakis I.G., Caratzoulas S., Meyer C.A., Kallrath J. (2005). Global optimization in the 21st century: advances and challenges. Comput. Chem. Eng. 29(6): 1185-1202

    Article  Google Scholar 

  13. Gill, P.E., Murray, W., Saunders, M.A., Wight, M.H.: User’s guide for npsol 5.0: A FORTRAN package for nonlinear programming. Technical Report SOL 86–1, Systems Optimization Laboratory, Stanford University (1998)

  14. Gill P.E., Murray W., Saunders M.A. (2002). SNOPT: An SQP algorithm for large-scale constrained optimization. SIAM J. Optim 12(4): 979-1006

    Article  Google Scholar 

  15. Glover F. (1977). Heuristics for integer programming using surrogate constraints. Decis. Sci. 8, 156-166

    Article  Google Scholar 

  16. Glover F. (1994). Tabu search for nonlinear and parametric optimization (with links to genetic algorithms). Discrete Appl. Math. 49, 231-255

    Article  Google Scholar 

  17. Glover F. (1998). A template for scatter search and path relinking. In: Hao J.K., Lutton E., Ronald E., Schoenauer M., Snyers D. (eds.) Artificial Evolution, Lecture Notes in Computer Science vol. 1363. Springer Verlag, Berlin, pp 13-54

    Google Scholar 

  18. Holmström K., Edvall M.M. (2004). The Tomlab optimization environment. In: Kallrath J., Basf A.B. (eds.) Modeling Languages in Mathematical Optimization. Kluwer Academic Publishers, Dordrecht, pp 369-378

    Google Scholar 

  19. Jones D.R. (2001). DIRECT global optimization algorithm. In: Floudas C.A., Pardalos P.M. (eds.) Encyclopedia of Optimization. Kluwer Academic Publishers, Dordrecht, pp 431-440

    Chapter  Google Scholar 

  20. Laguna M., Martí R. (2002). The OptQuest callable library. In: Voss S., Woodruff D. (eds.) Optimization Software Class Libraries. Kluwer Academic Publishers, Boston, pp 193-218

    Google Scholar 

  21. Laguna M., Martí R. (2003). Scatter Search: Methodology and Implementations in C. Kluwer Academic Publishers, Boston

    Google Scholar 

  22. Laguna M., Martí R. (2005). Experimental testing of advanced scatter search designs for global optimization of multimodal functions. J. Global Optim. 33, 235-255

    Article  Google Scholar 

  23. Mathworks, Matlab 6.5R13, Mathworks, Natick, MA (2004)

  24. Michalewicz Z., Logan T.D. (1994). Evolutionary operators for continuous convex parameter spaces. In: Sebald A.V., Fogel L.J. (eds.) Proceedings of the 3rd Annual Conference on Evolutionary Programming. World Scientific Publishing, River Edge, pp 84-97

    Google Scholar 

  25. Moles C.G., Gutierrez G., Alonso A.A., Banga J.R. (2003a). Integrated process design and control via global optimization: a wastewater treatment plant case study. Chem. Eng. Res. Des. 81(5): 507-517

    Article  Google Scholar 

  26. Moles C.G., Mendes P., Banga J.R. (2003b). Parameter estimation in biochemical pathways: a comparison of global optimization methods. Genome Res. 13(11): 2467-2474

    Article  Google Scholar 

  27. Panier E., Tits A.L. (1993). On combining feasibility, descent and superlinear convergence in inequality constrained optimization. Math. Program. 59, 261-276

    Article  Google Scholar 

  28. Runarsson T.P., Yao X. (2000). Stochastic ranking for constrained evolutionary optimization. IEEE Trans. Evol. Comput. 4, 284-294

    Article  Google Scholar 

  29. Runarsson T. P., Yao X. (2005). Search biases in constrained evolutionary optimization. IEEE Trans. Syst. Man Cybern. 35, 233-243

    Article  Google Scholar 

  30. Shimizu K. (1996). A tutorial review on bioprocess systems engineering. Comput. Chem. Eng. 20, 915-941

    Article  Google Scholar 

  31. Storn R., Price K. (1997). Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces. J. Global Optim. 11, 341-359

    Article  Google Scholar 

  32. Ugray Z., Lasdon L., Plummer J., Glover F., Kelly J., Martí R. (2005). A multistart scatter search heuristic for smooth NLP and MINLP problems. In: Rego C., Alidaee B.(eds.) Metaheuristic Optimization via Memory and Evolution: Tabu Search and Scatter Search. Kluwer Academic Publishers, Dordrecht, pp 25-58

    Chapter  Google Scholar 

  33. Wächter A., Biegler L.T. (2006). On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming. Math. Program. 106(1): 25-57

    Article  Google Scholar 

  34. Ye, Y.: Interior Algorithms for Linear, Quadratic and Linearly Constrained Non-linear programing. Phd Thesis, Stanford University (1987)

  35. Yuret, D.: From Genetic Algorithms to Efficient Optimization. A.I. Technical Report No. 1569. Massachusetts Insitute of Technology (1994)

Download references

Author information

Authors and Affiliations

  1. Process Engineering Group, Instituto de Investigaciones Marinas (C.S.I.C.), Eduardo Cabello 6, 36208, Vigo, Spain

    Jose A. Egea, María Rodríguez-Fernández & Julio R. Banga

  2. Departamento de Estadística e Investigación Operativa, Universitat de València, Dr. Moliner 50, 46100, Burjassot (Valencia), Spain

    Rafael Martí

Authors
  1. Jose A. Egea
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. María Rodríguez-Fernández
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Julio R. Banga
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Rafael Martí
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jose A. Egea.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Egea, J.A., Rodríguez-Fernández, M., Banga, J.R. et al. Scatter search for chemical and bio-process optimization. J Glob Optim 37, 481–503 (2007). https://doi.org/10.1007/s10898-006-9075-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-006-9075-3

Keywords

Search

Navigation