An evolutionary algorithm for solving bilevel programming problems using duality conditions. (English) Zbl 1264.90153

Summary: Bilevel programming is characterized by two optimization problems located at different levels, in which the constraint region of the upper level problem is implicitly determined by the lower level problem. This paper is focused on a class of bilevel programming with a linear lower level problem and presents a new algorithm for solving this kind of problems by combining an evolutionary algorithm with the duality principle. First, by using the prime-dual conditions of the lower level problem, the original problem is transformed into a single-level nonlinear programming problem. In addition, for the dual problem of the lower level, the feasible bases are taken as individuals in population. For each individual, the values of dual variables can be obtained by taking the dual problem into account, thus simplifying the single-level problem. Finally, the simplified problem is solved, and the objective value is taken as the fitness of the individual. Besides, when nonconvex functions are involved in the upper level, a coevolutionary scheme is incorporated to obtain global optima. In the computational experiment, 10 problems, smaller or larger-scale, are solved, and the results show that the proposed algorithm is efficient and robust.


90C29 Multi-objective and goal programming
90C60 Abstract computational complexity for mathematical programming problems
Full Text: DOI


[1] J. F. Bard, Practical Bilevel Optimization, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1998. · Zbl 1053.92504
[2] B. Colson, P. Marcotte, and G. Savard, “Bilevel programming: a survey,” Journal of Operations Research, vol. 3, no. 2, pp. 87-107, 2005. · Zbl 1134.90482
[3] M. Zhao and Z. Gao, “A globally convergent algorithm for solving the bilevel linear programming problem,” OR Transacton, vol. 9, no. 2, pp. 57-62, 2005.
[4] L. D. Muu and N. V. Quy, “A global optimization method for solving convex quadratic bilevel programming problems,” Journal of Global Optimization, vol. 26, no. 2, pp. 199-219, 2003. · Zbl 1053.90104
[5] J. B. E. Etoa, “Solving convex quadratic bilevel programming problems using an enumeration sequential quadratic programming algorithm,” Journal of Global Optimization, vol. 47, no. 4, pp. 615-637, 2010. · Zbl 1237.90176
[6] B. Colson, P. Marcotte, and G. Savard, “A trust-region method for nonlinear bilevel programming: algorithm and computational experience,” Computational Optimization and Applications, vol. 30, no. 3, pp. 211-227, 2005. · Zbl 1078.90041
[7] K.-M. Lan, U.-P. Wen, H.-S. Shih, and E. S. Lee, “A hybrid neural network approach to bilevel programming problems,” Applied Mathematics Letters, vol. 20, no. 8, pp. 880-884, 2007. · Zbl 1162.90514
[8] Y. Wang, Y. C. Jiao, and H. Li, “An evolutionary algorithm for solving nonlinear bilevel programming based on a new constraint-handling scheme,” IEEE Transactions on Systems, Man and Cybernetics Part C, vol. 35, no. 2, pp. 221-232, 2005.
[9] B. Liu, “Stackelberg-Nash equilibrium for multilevel programming with multiple followers using genetic algorithms,” Computers & Mathematics with Applications, vol. 36, no. 7, pp. 79-89, 1998. · Zbl 0947.90115
[10] S. K. Suneja and B. Kohli, “Optimality and duality results for bilevel programming problem using convexifactors,” Journal of Optimization Theory and Applications, vol. 150, no. 1, pp. 1-19, 2011. · Zbl 1229.90207
[11] J. Glackin, J. G. Ecker, and M. Kupferschmid, “Solving bilevel linear programs using multiple objective linear programming,” Journal of Optimization Theory and Applications, vol. 140, no. 2, pp. 197-212, 2009. · Zbl 1163.90020
[12] Z. Wan, G. Wang, and Y. Lv, “A dual-relax penalty function approach for solving nonlinear bilevel programming with linear lower level problem,” Acta Mathematica Scientia. Series B, vol. 31, no. 2, pp. 652-660, 2011. · Zbl 1240.90322
[13] H. I. Calvete, C. Galé, S. Dempe, and S. Lohse, “Bilevel problems over polyhedra with extreme point optimal solutions,” Journal of Global Optimization, vol. 53, no. 3, pp. 573-586, 2012. · Zbl 1251.90363
[14] U. P. Wen and S. T. Hsu, “Linear bi-level programming problems. A review,” Journal of the Operational Research Society, vol. 42, no. 2, pp. 125-133, 1991. · Zbl 0722.90046
[15] A. G. Mersha and S. Dempe, “Linear bilevel programming with upper level constraints depending on the lower level solution,” Applied Mathematics and Computation, vol. 180, no. 1, pp. 247-254, 2006. · Zbl 1102.90070
[16] C. Shi, J. Lu, G. Zhang, and H. Zhou, “An extended branch and bound algorithm for linear bilevel programming,” Applied Mathematics and Computation, vol. 180, no. 2, pp. 529-537, 2006. · Zbl 1102.65071
[17] R. J. Kuo and C. C. Huang, “Application of particle swarm optimization algorithm for solving bi-level linear programming problem,” Computers & Mathematics with Applications, vol. 58, no. 4, pp. 678-685, 2009. · Zbl 1189.90212
[18] Y. Wang, H. Li, and C. Dang, “A new evolutionary algorithm for a class of nonlinear bilevel programming problems and its global convergence,” INFORMS Journal on Computing, vol. 23, no. 4, pp. 618-629, 2011. · Zbl 1243.90208
[19] K. Deb and S. Sinha, “An efficient and accurate solution methodology for bilevel multi-objective programming problems using a hybrid evolutionary-local-search algorithm,” Journal Evolutionary Computation, vol. 18, no. 3, pp. 403-449, 2010.
[20] H. I. Calvete, C. Galé, and P. M. Mateo, “A new approach for solving linear bilevel problems using genetic algorithms,” European Journal of Operational Research, vol. 188, no. 1, pp. 14-28, 2008. · Zbl 1135.90023
[21] T. Hu, B. Huang, and X. Zhang, “A neural network approach for solving linear bilevel programming problem,” in Proceedings of the 6th ISNN Conference, vol. 56, pp. 649-658, AISC, 2009.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.