MIDACO Parallelization Scalability on 200 MINLP Benchmarks

Schlueter, Martin; Munetomo, Masaharu

doi:10.1515/jaiscr-2017-0012

Abstract

This contribution presents a numerical evaluation of the impact of parallelization on the performance of an evolutionary algorithm for mixed-integer nonlinear programming (MINLP). On a set of 200 MINLP benchmarks the performance of the MIDACO solver is assessed with gradually increasing parallelization factor from one to three hundred. The results demonstrate that the efficiency of the algorithm can be significantly improved by parallelized function evaluation. Furthermore, the results indicate that the scale-up behaviour on the efficiency resembles a linear nature, which implies that this approach will even be promising for very large parallelization factors. The presented research is especially relevant to CPU-time consuming real-world applications, where only a low number of serial processed function evaluation can be calculated in reasonable time.

References

[1] Babu B., Angira A., A differential evolution approach for global optimisation of minlp problems, In: Proceedings of the Fourth Asia Pacific Conference on Simulated Evolution and Learning (SEAL 2002), Singapore, 2002, pp. 880–884.
Search in Google Scholar Back to article
[2] Cardoso M.F., Salcedo R.L., Azevedo S.F., Barbosa D., A simulated annealing approach to the solution of MINLP problems, Computers Chem. Engng. 12(21), 1997, pp. 1349–1364.10.1016/S0098-1354(97)00015-X
Search in Google Scholar Back to article
[3] Costa L., Oliveira P., Evolutionary algorithms approach to the solution of mixed integer non-linear programming problems, Comput Chem Eng, 25(23), 2001, 257-266.10.1016/S0098-1354(00)00653-0
Search in Google Scholar Back to article
[4] Deep K., Krishna P.S., Kansal M.L., Mohan C., A real coded genetic algorithm for solving integer and mixed integer optimization problems. Appl. Math. Comput., 212(2), 2009, pp. 505–518.10.1016/j.amc.2009.02.044
Search in Google Scholar Back to article
[5] European Space Agency (ESA) and Advanced Concepts Team (ACT), Gtop database - global optimisation trajectory problems and solutions, Software available at http://www.esa.int/gsp/ACT/inf/op/globopt.htm, 2011.
Search in Google Scholar Back to article
[6] Glover F., Parametric tabu-search for mixed integer programs, Comput Oper Res 33(9), 2006, 24492494.10.1016/j.cor.2005.07.009
Search in Google Scholar Back to article
[7] Gupta S., Tan G., A scalable parallel implementation of evolutionary algorithms for multi-objective optimization on GPUs, Evolutionary Computation (CEC), IEEE Congress on, Sendai, 2015, pp. 1567–1574.10.1109/CEC.2015.7257074
Search in Google Scholar Back to article
[8] Quinn J.M., Parallel Programming in C with MPI and OpenMP, McGraw-Hill, 2003.
Search in Google Scholar Back to article
[9] GAMS MINLPlib - A collection of Mixed Integer Nonlinear Programming models. Washington, DC, USA; software available at http://www.gamsworld.org/minlp/minlplib.htm, 2016.
Search in Google Scholar Back to article
[10] Laessig J., Sudholt D., General upper bounds on the runtime of parallel evolutionary algorithms, Evolutionary Computation, vol. 22, no. 3, 2014, pp. 405-437.10.1162/EVCO_a_00114
Search in Google Scholar Back to article
[11] Liang B., Wang J., Jiang Y., Huang D., Improved Hybrid Differential Evolution-Estimation of Distribution Algorithm with Feasibility Rules for NLP/MINLP, Engineering Optimization Problems, Chin. J. Chem. Eng. 20(6), 2012, pp. 1074–1080.10.1016/S1004-9541(12)60589-8
Search in Google Scholar Back to article
[12] Mohamed A.W., An efficient modified differential evolution algorithm for solving constrained non-linear integer and mixed-integer global optimization problems. Int. J. Mach. Learn. & Cyber., 2015, pp. 1–19.10.1007/s13042-015-0479-6
Search in Google Scholar Back to article
[13] Munawar A., Redesigning Evolutionary Algorithms for Many-Core Processors Ph.D. Thesis, Graduate School of Information Science and Technology, Hokkaido University, Japan, 2012.
Search in Google Scholar Back to article
[14] Du X., Ni Y., Yao Z., Xiao R., High performance parallel evolutionary algorithm model based on MapReduce framework, Int. J. Computer Applications in Technology, Vol. 46, No. 3, 2013, pp. 290–296.10.1504/IJCAT.2013.052807
Search in Google Scholar Back to article
[15] Powell D., Hollingsworth J., A NSGA-II, web-enabled, parallel optimization framework for NLP and MINLP, Proceedings of the 9th annual conference on Genetic and evolutionary computation, 2007, pp. 2145–2150.10.1145/1276958.1277372
Search in Google Scholar Back to article
[16] Sakuray Pais M., Yamanaka K., Rodrigues Pinto E., Rigorous Experimental Performance Analysis of Parallel Evolutionary Algorithms on Multicore Platforms, In IEEE Latin America Transactions, vol. 12, no. 4, 2014, pp. 805–811.10.1109/TLA.2014.6868886
Search in Google Scholar Back to article
[17] Schlueter M., Egea J.A., Banga J.R., Extended ant-colony optimization for non-convex mixed integer nonlinear programming, Comput. Oper. Res. 36(7), 2009, 2217–2229.10.1016/j.cor.2008.08.015
Search in Google Scholar Back to article
[18] Schlueter M., Gerdts M., The Oracle Penalty Method. J. Global Optim. 47(2), 2010, 293–325.10.1007/s10898-009-9477-0
Search in Google Scholar Back to article
[19] Schlueter, M., Gerdts, M., Rueckmann J.J., A Numerical Study of MIDACO on 100 MINLP Benchmarks, Optimization 7(61), 2012, pp. 873–900.10.1080/02331934.2012.668545
Search in Google Scholar Back to article
[20] Schlueter M., Erb S., Gerdts M., Kemble S., Rueckmann J.J., MIDACO on MINLP Space Applications, Advances in Space Research, 51(7), 2013, 1116–1131.10.1016/j.asr.2012.11.006
Search in Google Scholar Back to article
[21] Schlueter M., MIDACO Software Performance on Interplanetary Trajectory Benchmarks, Advances in Space Research, 54(4), 2014, 744–754.10.1016/j.asr.2014.05.002
Search in Google Scholar Back to article
[22] Schlueter M., MIDACO Solver - Global Optimization Software for Mixed Integer Nonlinear Programming, Software available at http://www.midaco-solver.com, 2016.
Search in Google Scholar Back to article
[23] Schlueter M., Munetomo M., Numerical Assessment of the Parallelization Scalability on 200 MINLP Benchmarks, Proc. of the IEEE-CEC2016 Conference, Vancouver, Canada, 2016.10.1109/CEC.2016.7743877
Search in Google Scholar Back to article
[24] K. Schittkowski, A Collection of 200 Test Problems for Nonlinear Mixed-Integer Programming in Fortran (User Guide), Report, Department of Computer Science, University of Bayreuth, Bayreuth, 2012.
Search in Google Scholar Back to article
[25] K. Schittkowski, NLPQLP - A Fortran implementation of a sequential quadratic programming algorithm with distributed and non-monotone line search (User Guide), Report, Department of Computer Science, University of Bayreuth, Bayreuth, 2009.
Search in Google Scholar Back to article
[26] K. Socha and M. Dorigo, Ant colony optimization for continuous domains, Eur. J. Oper. Res. 85, 2008, pp. 1155–1173.10.1016/j.ejor.2006.06.046
Search in Google Scholar Back to article
[27] Sudholt D., Parallel Evolutionary Algorithms, In Janusz Kacprzyk and Witold Pedrycz (Eds.): Handbook of Computational Intelligence, Springer, 2015.10.1007/978-3-662-43505-2_46
Search in Google Scholar Back to article
[28] Wasanapradit T., Mukdasanit N., Chaiyaratana N., Srinophakun T., Solving mixed-integer nonlinear programming problems using improved genetic algorithms, Korean J. Chem. Eng. 28(1), 2011, 32–40.10.1007/s11814-010-0323-3
Search in Google Scholar Back to article
[29] Yiqing L., Xigang Y., Yongjian L., An improved PSO algorithm for solving non-convex NLP/MINLP problems with equality constraints, Comp. Chem. Eng. 3(31), 2007, 153–162.10.1016/j.compchemeng.2006.05.016
Search in Google Scholar Back to article
[30] Young C.T., Zheng Y., Yeh C.W., Jang S.S., Information-guided genetic algorithm approach to the solution of MINLP problems, Ind. Eng. Chem. Res. 46, 2007, pp. 1527–1537.10.1021/ie060727h
Search in Google Scholar Back to article
[31] Yingyong Z., Yongde Z., Qinghua L., Jingang J., Guangbin Y., Improved Multi-objective Genetic Algorithm Based on Parallel Hybrid Evolutionary Theory, International Journal of Hybrid Information Technology Vol.8, No.1, 2015, pp. 133–140.10.14257/ijhit.2015.8.1.11
Search in Google Scholar Back to article
[32] Yue T., Guan-Zheng T., Shu-Guang D., Hybrid particle swarm optimization with chaotic search for solving integer and mixed integer programming problems. J. Central South Univ., 2014, 21:2731–2742.10.1007/s11771-014-2235-6
Search in Google Scholar Back to article

MIDACO Parallelization Scalability on 200 MINLP Benchmarks

Abstract

Paradigm

My account