Designing of a mat-heuristic algorithm for solving bi-level optimization problems

Document Type : Article


Department of Industrial Engineering, Faculty of Engineering, Shahed University, Tehran, Iran


In this paper, a new algorithm for solving bi-level optimization problems is presented. This algorithm can obtain the optimal or near-optimal solution for any bi-level optimization problem. The decision variables of the first and second level models can be both integers and continuous. In this method, by solving a certain number of the bi-objective programming model and then solving the corresponding second-level model, a bi-level feasible solution that is either optimal or near-optimal is identified. To evaluate the efficiency of the algorithm, the value of the objective function, as well as its computation time in different instances, are compared with exact methods as well as evolution-based methods. The numerical results confirm the high efficiency of the proposed algorithm.


1. Zhang, Y., Berman, O., Marcotte, P., et al. "A bilevel model for preventive healthcare facility network design with congestion", IIE Transactions, 42(12), pp. 865- 880 (2010).
2. Zhou, L., Lin, Y., Wang, X., et al. "Model and algorithm for bilevel multisized terminal location-routing problem for the last mile delivery", International Transactions in Operational Research, 26(1), pp. 131- 156 (2019).
3. Beresnev, V. and Melnikov, A. "Exact method for the capacitated competitive facility location problem", Computers & Operations Research, 95, pp. 73-82 (2018).
4. Cao, D. and Chen, M. "Capacitated plant selection in a decentralized manufacturing environment: a bilevel optimization approach", European Journal of Operational Research, 169(1), pp. 97-110 (2006).
5. Calvete, H.I., Gale, C., and Iranzo, J.A. "Planning of a decentralized distribution network using bilevel optimization", Omega, 49, pp. 30-41 (2014).
6. Zaheri, F., Zandieh, M., and Taghavifard, M.T. "Bilevel programming for supplier selection under quantity discount policy", Scientia Iranica, 24(4), pp. 2095-2104 (2017).
7. Brown, G., Carlyle, M., Diehl, D., et al. "A twosided optimization for theater ballistic missile defense", Operations Research, 53(5), pp. 745-763 (2005).
8. Amouzegar, M.A. and Moshirvaziri, K. "Determining optimal pollution control policies: An application of bilevel programming", European Journal of Operational Research, 119(1), pp. 100-120 (1999).
9. Kaheh, Z., Baradaran Kazemzadeh, R., and Sheikh- El-Eslami, M.K. "A solution based on fuzzy max-min approach to the bi-level programming model of energy and exiramp procurement in day-ahead market", Scientia Iranica, 27(2), pp. 846-861 (2020).
10. Sadati, S.M.B., Moshtagh, J., Shafie-khah, M., et al. "Operational scheduling of a smart distribution system considering electric vehicles parking lot: A bi-level approach", Inter. J. Elec. Pow. & Ener. Sys., 105, pp. 159-178 (2019).
11. Basciftci, B. and Van Hentenryck, P. "Bilevel optimization for on-demand multimodal transit systems", International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Springer, pp. 52-68 (Sept. 2020).
12. Stouraitis, T., Chatzinikolaidis, I., Gienger, M., et al. "Online hybrid motion planning for dyadic collaborative manipulation via bilevel optimization", IEEE Transactions on Robotics, 36(5), pp. 1452-1471 (2020).
13. Antil, H., Di, Z.W., and Khatri, R. "Bilevel optimization, deep learning and fractional Laplacian regularizatin with applications in tomography", Inverse Problems, 36(6), 064001 (2020).
14. Sinha, A., Malo, P., and Deb, K. "A review on bilevel optimization: From classical to evolutionary approaches and applications", IEEE Transactions on Evolutionary Computation, 22(2), pp. 276-295 (2017).
15. Bagloee, S.A., Asadi, M., Sarvi, M., et al. "A hybrid machine-learning and optimization method to solve bilevel problems", Expert Systems with Applications, 95, pp. 142-152 (2018).
16. Zhao, X., Zheng, Y., and Wan, Z. "Interactive intuitionistic fuzzy methods for multilevel programming problems", Expert Systems with Applications, 72, pp. 258-268 (2017).
17. Sinha, A., Lu, Z., Deb, K., et al. "Bilevel optimization based on iterative approximation of multiple mappings", Journal of Heuristics, 26(2), pp. 151-185 (2020).
18. Hejazi, S.R., Memariani, A., Jahanshahloo, G., et al. "Linear bilevel programming solution by genetic algorithm", Computers & Operations Research, 29(13), pp. 1913-1925 (2002).
19. Sinha, A., Malo, P., and Deb, K. "Evolutionary algorithm for bilevel optimization using approximations of the lower level optimal solution mapping", European Journal of Operational Research, 257(2), pp. 395-411 (2017).
20. Wang, Y., Li, H., and Dang, C. "A new evolutionary algorithm for a class of nonlinear bilevel programming problems and its global convergence", INFORMS Journal on Computing, 23(4), pp. 618-629 (2011).
21. Sharma, A. "Optimistic variants of single-objective bilevel optimization for evolutionary algorithms", International Journal of Computational Intelligence and Applications, 19(03), p. 2050020 (2020).
22. Shi, C., Lu, J., and Zhang, G. "An extended Kuhn- Tucker approach for linear bilevel programming", Applied Mathematics and Computation, 162(1), pp. 51- 63 (2005).
23. Zare, M.H., Borrero, J.S., Zeng, B., et al. "A note on linearized reformulations for a class of bilevel linear integer problems", Annals of Operations Research, 272(1-2), pp. 99-117 (2019).
24. Dempe, S. and Zemkoho, A.B. "KKT reformulation and necessary conditions for optimality in nonsmooth bilevel optimization", SIAM Journal on Optimization, 24(4), pp. 1639-1669 (2014).
25. Tahernejad, S., Ralphs, T.K., and DeNegre, S.T. "A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation", Mathematical Programming Computation, 12(4), pp. 529-568 (2020).
26. Aazami, A. and Saidi-Mehrabad, M. "Benders decomposition algorithm for robust aggregate production planning considering pricing decisions in competitive environment: A case study", Scientia Iranica, 26(5), pp. 3007-3031 (2019).
27. Kuo, R.J. and Han, Y.S. "A hybrid of genetic algorithm and particle swarm optimization for solving bilevel linear programming problem - A case study on supply chain model", Applied Mathematical Modelling, 35(8), pp. 3905-3917 (2011).