Study On The Algorithms Of The Bilevel Programming Problems

This paper discusses bilevel programming problems, including bilevel linear programming, bilevel nonlinear programming and mixed integer bilevel linear programming. The mathematical model, definition and some properties of them are discussed, some algorithms to solve them are proposed.At the beginning, the paper introduces the derivation, definition, main characteristics, mathematical model, applications of bilevel programming and the progress of research on solution algorithms.The paper researches the mathematical model, definition and some basically theory of the bilevel linear programming, which all objective functions and constraints are linear, and the decision variables are continuous. The important property is that the feasible region is composed of several surfaces of the constraint region, and the optimal solution occurs at an extreme point of the constraint region. The paper discusses the optimization conditions of the bilevel linear programming. Based on the optimization conditions, a global convergent algorithm is proposed.The bilevel nonlinear programming, which the upper-level objective function is nonlinear differentiable, the lower-level objective function is convex quadratic and all constraints are linear, is discussed. Using the K-T condition and the penalty function principle, the problem is transformed into a nonlinear programming by appending the complementarity constraints of lower-level problem as a penalty to the upper-level objective function. Using the Frank-Wolfe algorithm of nonlinear programming, an optimal algorithm to finding K-T point of bilevel nonlinear programming is presented by solving a series of nonlinear programs.The problem of the mixed integer bilevel linear programming becomes complicated because of the discrete variables. The paper researches the mixed integer bilevel linear programming, which the upper-level decision variable is integer and the lower-level decision variable is continuous. The paper discusses the structure of solution and finds the property that the feasible solutions are lying to the boundary of the constraint region, which leads to an enumeration scheme being proposed. The paper gives the theory of branch and bound to the mixed integer bilevel linear programming which upper-level decision variable is 0-1 and the lower-level decision variable is continuous, a branch and bound algorithm is presented for finding the global optimal solution of the problem.Finally, the paper summarizes the obtained results and prospects the future research.