A novel approach for solving bi-level mono-objective and multi-objective programming problems using evolutionary algorithms

Wafa Bouguern; Smail Addoune; Hanene Debbiche

doi:10.18540/jcecvl10iss9pp20661

Auteurs

Wafa Bouguern Mathematical Analysis and Applications Laboratory, Department of Mathematics, University Mohamed El Bachir El Ibrahimi of Bordj Bou Arreridj, El Anasser 34030, Algeria https://orcid.org/0000-0002-5565-3581
Smail Addoune Mathematical Analysis and Applications Laboratory, Department of Mathematics, University Mohamed El Bachir El Ibrahimi of Bordj Bou Arreridj, El Anasser 34030, Algeria
Hanene Debbiche Mathematical Analysis and Applications Laboratory, Department of Mathematics, University Mohamed El Bachir El Ibrahimi of Bordj Bou Arreridj, El Anasser 34030, Algeria

DOI :

https://doi.org/10.18540/jcecvl10iss9pp20661

Mots-clés :

Nonlinear bi-level programming, Multicriteria optimization, optimization

Résumé

Bi-level programming problems (BLP) constitute an important class of non-convex optimization problems, which makes it challenging to find a global optimal solution. In this article, we propose an efficient technique to solve this category of problems. We reformulated the initial problem as a single-level optimization problem using the optimal value function of the lower-level problem. To solve the latter, we employed a technique based on -dense curves to approximate the value function of the lower-level problem. Two evolutionary algorithms were then used to solve the reformulated problem. Furthermore, we extended our method to address multi-objective bi-level programming problems with a single objective at the upper level and multiple objectives at the lower level, known as a semi-vectorial bi-level programming problem. Several numerical experiments on nonlinear BLP show the outstanding efficiency of our approach.

Téléchargements

Les données relatives au téléchargement ne sont pas encore disponibles.

Références

Anandalingam, G., & White, D. (1990). A solution method for the linear static stackelberg problem using penalty functions. IEEE, 35, 1170-1173. doi: https://doi.org/10.1109/9.58565

Angelo, S., Krempser, E., & Barbosa, H. J. (2014). Differential evolution assisted by a surrogate model for bilevel programming problems. 2014 IEEE Congress on Evolutionary, Computation (CEC), 1784–1791. doi: https://doi.org/10.1109/CEC.2014.6900529

Bard, J. F., & Moore, J. T. (1990). A branch and bound algorithm for the bi-level programming problem. SIAM Journal on Scientific and Statistical Computing, 11, 128-290. doi: https://doi.org/10.1137/0911017

Butz, A. (1972). Solution of nonlinear equations with space filling curves. Journal of Mathematical Analysis and Applications, 37, 351-383. doi: https://doi.org/10.1016/0022-247X(72)90280-6

Dempe, S., & Dutta, J. (2012). Is bi-level programming a special case of a mathematical program with complementarity constraints?. Mathematical Programming, 131, 37-48. doi: https://doi.org/10.1007/s10107-010-0342-1

Dempe, S., & Franke, S. (2019). Solution of bi-level optimization problems using the kkt approach.Optimization, 68,1471-1489. doi: https://doi.org/10.1080/02331934.2019.1581192

Dempe, S., & Mehlitz, P.(2019). Semi-vectorial bi-level programming versus scalar bi-level programming. Optimization,157,657-679 .doi:https://doi.org/1 0.1080/023319 34.2019.1625 900

Dempe, S., & Zemkoho, A. (2013). New optimality conditions for the semi-vectorial bi-level optimization problem. Journal of Optimization Theory and Applications, 157, 54-74. doi: https://doi.org/10.1007/s10957-012-0161-z

Ehrgott, M. (2005). Multicriteria optimization. Springer Science and Business Media, 491 . doi: https://doi.org/10.1007/3-540-27659-9

Gupta, A., & Ong, Y. S. (2015). An evolutionary algorithm with adaptive scalarization for multi-objective bi-level programs. 2015 IEEE Congress on Evolutionary Computation (CEC), 1636-1642. https://doi:10.1109/CEC.2015.7257083

Jane, J. Y. (2005). Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints. Journal of Mathematical Analysis and Applications, 307, 350-369. doi: https://doi.org/10.1016/j.jmaa.2004.10.032

Jialin, H., Guangquan, Z., Yaoguang, H., & Jie, L. (2016). A solution to bi/tri-level programming problems using particle swarm optimization. Information Sciences, 370, 519-537. doi: https://doi.org/10.1016/j.ins.2016.08.022

Joao, A. M., & Paulo, C. J. (2014). An algorithm based on particle swarm optimization for multi-objective bi-level linear problems. Applied Mathematics and Computation, 247, 547-561. doi: https://doi.org/10.1016/j.amc.2014.09.013

João, A. M., Antunes, C. H., & Carrasqueira, P. (2015). A pso approach to semi-vectorial bi-level programming: pessimistic, optimistic and deceiving solutions. Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, 599-606. doi: https://doi.org/10.1145/2739480.2754644

Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. Proceedings of ICNN’95- international conference on neural networks, 4, 1942-1948. doi: https://doi.org/10.1109/ICNN.1995 .488968

Li, H., & L.Zhang. (2021). An efficient solution strategy for bi-level multi-objective optimization problems using multi-objective evolutionary algorithm. Soft Computing, 25, 8241-8261. doi: https://doi.org/10.1007/s00500-021-05750-0

Lin, G. H., Xu, M., & Ye, J. J. (2014). On solving simple bi-level programs with a non convex lower level program. Mathematical Programming, 144, 277-305. doi: https://doi.o rg/10.10 07/s10107-013-0633-4

Ma, L., & Wang, G. (2020). A solving algorithm for nonlinear bi-level programing problems based on human evolutionary model. Algorithms, 13, 260-272. doi: https://doi. org/10.3390/a13100260

Mathieu, R., Pittard, L., & Anandalingam, G. (1994). Genetic algorithm based approach to bi-level linear programming. RAIRO-Operations Research, 28, 1-21.

Mirjalili, S., Mirjalili, S. M., & Lewis, A. (2014). Grey wolf optimizer. Advances in Engineering Software, 69, 46-61. doi: https://doi.org/10.1016/j.advengsoft.2013.12.007

Mitsos, A., & Barton, P. (2006). A test set for bi-level programs. Available at https://www.researchgate.net/publication/228455 291 .

Mora, G., & Cherruault, Y. (1997). Characterization and generation of _-dense curves. Computers and Mathematics with Applications, 33, 83-91. doi: https://doi.org/10.1016/S0898-1221(97)00067-9

Mora, G., & Mora-Porta, G. (2005). Dimensionality reducing multiple integrals by alpha-dense curves. International Journal of Pure and Applied Mathematics, 22, 103-114.

Nouri, A., Abdenacer, N., & Sahraoui, D. (2023). Accurate range-based distributed localization of wireless sensor nodes using grey wolf optimizer. The Journal of Engineering and Exact Sciences, 9, 15920–01e. doi: https://doi.org/10.18540/jcecvl9iss4pp15920-01e

Oduguwa, V., & Roy, R. (2002). Bi-level optimisation using genetic algorithm. Proceedings 2002 IEEE International Conference on Artificial Intelligence Systems, 322-327. doi: https://doi.org/10.1109/ICAIS.2002.1048121

Outrata, J. V. (1990). On the numerical solution of a class of stackelberg problems. Zeitschrift für Operations Research, 34, 255-277. doi: https://doi.org/10.1007/BF01416737

Ruuska, S., & Miettinen, K. (2012). Constructing evolutionary algorithms for bi-level multiobjective optimization. 2012 IEEE congress on evolutionary computation, 1-7. doi: https://doi.org/10.1109/CEC.2012.6256156

Shimizu, K., & Aiyoshi, E. (1981). A new computational method for stackelberg and min-max problems by use of a penalty method. IEEE Transactions on Automatic Control, 26, 460-466. doi: https://doi.org/10.1109/TAC.1981.1102607

Srivastava, S., & Sahana, S. K. (2019). Application of bat algorithm for transport network design problem. Applied Computational Intelligence and soft computing, 2019, 9864090. doi: https://doi.org/10.1155/2019/9864090

Stephan, D., Joydeep, D., & Mordukhovich, B. (2007). New necessary optimality conditions in optimistic bi-level programming. Optimization, 56, 577-604. doi: https ://doi.org/ 10.108 0/ 02331930701617551

Xu, M., & Ye, J. J. (2014). A smoothing augmented lagrangian method for solving simple bi-level programs. Computational Optimization and Applications, 59, 353-377. doi: http s://do i.org/ 10.1007/s10589-013-9627-7

Ye, J. J., & Zhu, D. L. (1995). Optimality conditions for bi-level programming problems. Optimization, 33, 9-27. doi: https://doi.org/10.1080/02331939508844060

Zemkoho, A., & Zhou, S. (2021). Theoretical and numerical comparison of the karush–Kuhn tucker and value function reformulations in bi-level optimization. Computational Optimization and Applications, 78, 625-674. doi: https://doi.org/10.1007/s10589-020-00250-7

Zhang, T., Chen, Z., & Chen, J. (2017). A cooperative coevolution pso technique for complex bilevel programming problems and application to watershed water trading decision making problems. Journal of Nonlinear Sciences and Applications(JNSA), 10. doi: https://doi.org/10 .224 36 /jns a .010.04.65

Zhao, Z., & Gu, X. (2006). Particle swarm optimization based algorithm for bi-level programming problems. Sixth International Conference on Intelligent Systems Design and Applications, 2, 951-956. doi: https://doi.org/10.1109/ISDA.2006.253740

Ziadi, R., & Bencherif-Madani, A. (2023). A mixed algorithm for smooth global optimization. Journal of Mathematical Modeling, 11, 207-228. doi: http s://do i.org/10. 22124/JM M.202 2.23133.2061