Solving large numerical optimization problems in HPC with Python

ABSTRACT

Numerical optimization is a complex problem in which many different algorithms can be used. Distributed metaheuristics have received attention but they normally focus on small problems. Many large scientific problems can take advantage of these techniques to find optimal solutions for the problems. However, solving large scientific problems presents specific issues that traditional implementations of metaheuristics do not tackle. This research presents a large parallel optimization solver that uses Python to follow a generic model that can be easily extended with new algorithms. It also makes extensive use of NumPy for an efficient utilization of the computational resources and MPI4py for communication in HPC environments. The presented model has proven to be an excellent approach for solving very large problems in an efficient manner while using the computational resources in different HPC environments adequately.

References

1. F.-A. Fortin, F.-M. De Rainville, M.-A. Gardner, M. Parizeau, and C. Gagné, "DEAP: Evolutionary algorithms made easy," Journal of Machine Learning Research, vol. 13, pp. 2171--2175, jul 2012.
2. Y. Hold-Geoffroy, O. Gagnon, and M. Parizeau, "Once you SCOOP, no need to fork," in Proceedings of the 2014 Annual Conference on Extreme Science and Engineering Discovery Environment, ser. XSEDE '14. New York, NY, USA: ACM, 2014, pp. 60:1--60:8. {Online}. Available: http://dx.doi.org/10.1145/2616498.2616565
3. "inspyred: Bio-inspired algorithms in Python," http://aarongarrett.github.io/inspyred/, 2015, {Online; accessed 22-Sep-2015}.
4. S. Cahon, N. Melab, and E.-G. Talbi, "ParadisEO: A framework for the reusable design of parallel and distributed metaheuristics," Journal of Heuristics, vol. 10, no. 3, pp. 357--380, May 2004. {Online}. Available: http://dx.doi.org/10.1023/B: HEUR.0000026900.92269.ec
5. B. Gasbaoui and B. Allaoua, "Ant colony optimization applied on combinatorial problem for optimal power flow solution," 2009.
6. V. Maniezzo, T. Sttzle, and S. Vo, Matheuristics: Hybridizing Metaheuristics and Mathematical Programming, 1st ed. Springer Publishing Company, Incorporated, 2009. {Online}. Available: http://dx.doi.org/10.1007/978-1-4419-1306-7
7. A. Gómez-Iglesias, A. T. Ernst, and G. Singh, "Scalable multi swarm-based algorithms with lagrangian relaxation for constrained problems," in 12th IEEE International Conference on Trust, Security and Privacy in Computing and Communications, TrustCom 2013 / 11th IEEE International Symposium on Parallel and Distributed Processing with Applications, ISPA-13 / 12th IEEE International Conference on Ubiquitous Computing and Communications, IUCC-2013, Melbourne, Australia, July 16-18, 2013. IEEE Computer Society, 2013, pp. 1073--1080. {Online}. Available: http://dx.doi.org/10.1109/TrustCom.2013.241
8. O. Brent, D. R. Thiruvady, A. Gomez-Iglesias, and R. Garcia-Flores, "A parallel lagrangian-aco heuristic for project scheduling," in Proceedings of the IEEE Congress on Evolutionary Computation, CEC 2014, Beijing, China, July 6-11, 2014. IEEE, 2014, pp. 2985--2991. {Online}. Available: http://dx.doi.org/10.1109/CEC.2014.6900504
9. E. D. Dolan, J. J. Moré, and T. S. Munson, "Benchmarking optimization software with cops 3.0," in MATHEMATICS AND COMPUTER SCIENCE DIVISION, ARGONNE NATIONAL LABORATORY, 2004.
10. A. Gómez-Iglesias, F. Castejón, and M. A. Vega-Rodríguez, "Distributed bees foraging-based algorithm for large-scale problems," in 25th IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2011, Anchorage, Alaska, USA, 16-20 May 2011 - Workshop Proceedings. IEEE, 2011, pp. 1950--1960. {Online}. Available: http://dx.doi.org/10.1109/IPDPS.2011.355
11. A. Gómez-Iglesias, M. A. Vega-Rodríguez, and F. Castejón, "Distributed and asynchronous solver for large CPU intensive problems," Appl. Soft Comput., vol. 13, no. 5, pp. 2547--2556, 2013. {Online}. Available: http://dx.doi.org/10.1016/j.asoc.2012.11.031
12. D. Karaboga and B. Basturk, "A powerful and efficient algorithm for numerical function optimization: Artificial bee colony (abc) algorithm," J. of Global Optimization, vol. 39, no. 3, pp. 459--471, Nov. 2007. {Online}. Available: http://dx.doi.org/10.1007/s10898-007-9149-x
13. M. Dorigo, V. Maniezzo, and A. Colorni, "Ant system: optimization by a colony of cooperating agents," Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, vol. 26, no. 1, pp. 29--41, Feb 1996. {Online}. Available: http://dx.doi.org/10.1109/3477.484436
14. S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, "Optimization by simulated annealing," SCIENCE, vol. 220, no. 4598, pp. 671--680, 1983. {Online}. Available: http://dx.doi.org/10.1126/science.220.4598.671
15. "Stampede cluster," https://www.tacc.utexas.edu/stampede/, 2015, {Online; accessed 22-Sep-2015}.
16. "Bragg cluster," https://wiki.csiro.au/display/ASC/CSIRO+Accelerator+Cluster+-+Bragg, 2015, {Online; accessed 22-Sep-2015}.
17. "Euler cluster," http://rdgroups.ciemat.es/en_US/web/sci-track/euler, 2015, {Online; accessed 22-Sep-2015}.
18. S. P. Hirshman and G. H. Neilson, "External inductance of an axisymmetric plasma," Physics of Fluids, vol. 29, no. 3, pp. 790--793, 1986. {Online}. Available: http://dx.doi.org/10.1063/1.865934
19. C. C. Hegna and N. Nakajima, "On the stability of mercier and ballooning modes in stellarator configurations," Physics of Plasmas, vol. 5, no. 1336, pp. 1336--1344, 1998. {Online}. Available: http://dx.doi.org/10.1063/1.872793
20. R. Sanchez, S. P. Hirshman, J. C. Whitson, and A. S. Ware, "COBRA: an optimized code for fast analysis of ideal ballooning stability of three-dimensional magnetic equilibria," Journal of Computational Physics, vol. 161, no. 2, pp. 576--588, 2000. {Online}. Available: http://dx.doi.org/10.1006/jcph.2000.6514
21. C. Alejaldre et al., "First plasmas in the TJ-II flexible heliac," Plasma Physics and Controlled Fusion, vol. 41, no. 3A, p. A539, 1999. {Online}. Available: http://dx.doi.org/10.1088/0741-3335/41/3A/047
22. V. Erckmann, H. J. Hartfuss, M. Kick, H. Renner, J. Sapper, F. Schauer, E. Speth, F. Wesner, F. Wagner, M. Wanner, A. Weller, and H. Wobig, "The W7-X project: scientific basis and technical realization," in Fusion Engineering, 1997. 17th IEEE/NPSS Symposium, vol. 1. San Diego, California: IEEE, Oct 1997, pp. 40--48. {Online}. Available: http://dx.doi.org/10.1109/FUSION.1997.685662
23. M. Cárdenas-Montes, M. A. Vega-Rodríguez, J. J. Rodríguez-Vázquez, and A. Gómez-Iglesias, "A comparison exercise on parallel evaluation of rosenbrock function," in Genetic and Evolutionary Computation Conference, GECCO 2015, Madrid, Spain, July 11--15, 2015, Companion Material Proceedings, J. L. J. Laredo, S. Silva, and A. I. Esparcia-Alcázar, Eds. ACM, 2015, pp. 1361--1362. {Online}. Available: http://doi.acm.org/10.1145/2739482.2764641

Index Terms

• Computer systems organization

  • Dependable and fault-tolerant systems and networks

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Mathematics of computing

  • Mathematical analysis

    • Mathematical optimization

• Networks

  • Network performance evaluation

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language types

• Theory of computation

  • Design and analysis of algorithms

    • Mathematical optimization