A Genetic Algorithm for Solving Linear-Quadratic Bilevel Program-Ming Problems


Article Preview

In this paper, we focus on a special linear-quadratic bilevel programming problem in which the follower’s problem is a convex-quadratic programming, whereas the leader’s functions are linear. At first, based on Karush-Kuhn-Tucher(K-K-T) conditions, the original problem is transformed into an equivalent nonlinear programming problem in which the objective and constraint functions are linear except for the complementary slack conditions. Then, a genetic algorithm is proposed to solve the equivalent problem. In the proposed algorithm, the individuals are encoded in two phases. Finally, the efficiency of the approach is demonstrated by an example.



Edited by:

Wenya Tian and Linli Xu






H. C. Li and Y. P. Wang, "A Genetic Algorithm for Solving Linear-Quadratic Bilevel Program-Ming Problems", Advanced Materials Research, Vol. 186, pp. 626-630, 2011

Online since:

January 2011




[1] B. Colson, P. Marcotte, G. Savard: An overview of bilevel optimization. Annals of Operations Research Vol. 153 (2007), p.235–256.

DOI: 10.1007/s10479-007-0176-2

[2] J. F. Bard: Practical Bilevel Optimization( Kluwer Academic Publishers, The Netherlands 1998).

[3] Suh-Wen Chiou: A bi-level programming for logistics network design with system optimized flows. Information Sciences Vol 179 (2009), pp.2434-2441.

DOI: 10.1016/j.ins.2009.03.005

[4] 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(2005), pp.211-227.

DOI: 10.1007/s10589-005-4612-4

[5] J. B. E. Etoa: Solving convex quadratic bilevel programming problems using an enumeration sequential quadratic programming. J. Glob. Optim. Vol. 47(2010), pp.615-637.

DOI: 10.1007/s10898-009-9482-3

[6] Kuen-Ming Lan, Ue-Pyng Wen and Hsu-Shih Shih, et al: A hybrid neural network approach to bilevel programming problems, Applied Mathematics Letters Vol. 20(2007), pp.880-884.

DOI: 10.1016/j.aml.2006.07.013

[7] Tiesong Hu, Xuning Guo , Xiang Fu and Yibing Lv: A neural network approach for solving linear bilevel programming problem, Knowledge-Based Systems Vol. 23 (2010) pp.239-242.

DOI: 10.1016/j.knosys.2010.01.001

[8] Guangmin Wang, Zhongping Wan and Xianjia Wang: Genetic algorithm based on simplex method for solving linear-quadratic bilevel programming problem. Computers and Mathematics with Applications Vol. 56 (2008), p.2550–2555.

DOI: 10.1016/j.camwa.2008.05.006

[9] H. I. Calvete, C. Gale and P. M. Mateo: A new approach for solving linear bilevel problems using genetic algorithms. European Journal of Operational Research, Vol. 188(2008), pp.14-28.

DOI: 10.1016/j.ejor.2007.03.034

[10] Yuping Wang, Yong-Chang Jiao and Hong Li: An evolutionary algorithm for solving nonlinear bilevel programming based on a new constraint-handling scheme. IEEE Trans. on Systems, Man, and Cybernetics-Part C, Vol. 35(2005), pp.221-232.

DOI: 10.1109/tsmcc.2004.841908

[11] Guangcheng Zhang: Computational Methods for Nonlinear Optimization (Higher Education Press, Beijing 2005).

In order to see related information, you need to Login.