Solving Method for a Class of Bilevel Linear Programming based on Genetic lgorithms^{∗ }

# G. Wang

†

# Z. Wan^{‡ }and X. Wang

Abstract

The paper studies and designs an genetic algorithm (GA) of the bilevel linear program- ming problem (BLPP) by constructing the fitness function of the upper-level programming problem based on the definition of the feasible degree. This GA avoids the use of penalty function to deal with the constraints, by changing the randomly generated initial population into an initial population satisfying the constraints in order to improve the ability of the GA to deal with the constraints. Finally, the numerical results of some examples indicate the feasibility and e ectiveness of the proposed method. Key words: bilevel linear programming, genetic algorithm, fitness function AMS Subject Classi cation 65K05 90C99 93A13

1

## Introduction

Bilevel linear programming problem is one of the basic types of bilevel systems. Although the objective function and the constraints of the upper-level and lower-level problems of BLPP are all linear, the BLPP is neither continuous everywhere nor convex for the objective function of the upper-level problem is decided by the solution function of the lower-level problem which, gener- ally speaking, is neither linear nor differentiable. Bialas and Karwan proved the non-convexity of the upper-level problem with practical example [1]. Bard Ben-Ayed and Blair proved BLPP is a NP-Hard problem [2, 3]. Besides, Hansen, Jaumard and Savard proved BLPP is a strongly NP-Hard problem [4]. Later, Vicente,Savard and Judice declared it is a NP-Hard problem to find the local optimal solution of BLPP [5].

At present, the various algorithms developed for solving the BLPP can be classified into the following categories:

1.

Extreme-point search method. It mainly includes K-best algorithm from Bialas and Kar- wan, Wen and Bialas [1, 7, 8], Grid-search algorithm from Bard [9, 10], etc.

2.

Transformation method. It mainly includes complementary-pivot algorithm from Judice and Faustino, Candler and Townsley, Onal [11, 12, 13, 14], branch-and-bound algorithm

Supported by the National Natural Science Foundation 60274048) and the Doctoral Foundation in Ministry of Education of China 20020486035) and the Huazhong Grid Bureau of National Electric Power Company.

†

Graduate Student, School of Mathematics and Statistics, Wuhan Univ., Wuhan 430072 China.

‡

Corresponding author. E-mail:zpwan@public.wh.hb.cn. Professor, School of Mathematics and Statistics,

Wuhan Univ., Wuhan 430072 China. ^{§}Professor, Institute of Systems Engineering, Wuhan Univ., Wuhan,430072 China.

1