Multilevel optimization problems are mathematical programs which have a subset of decision variables constrained to be an optimal solution of other programs parameterized by their remaining variables. A special case of multi-level optimization is bi-level optimization program which has received most of the attention in the literature [1]. Bi-level optimization is a hierarchical optimization problem where the set of all variables decisions are partitioned. In this problem the set of all variables is partitioned between two vectors and where is to be chosen as an optimal solution of a second mathematical programming problem parameterized in . In two-level hierarchical programming, two decision makers are considered, the leader decision maker and the follower decision maker. Each decision maker acting in sequence to optimize his own objective function. The leader examines the reaction of the follower for each feasible choice of and the resulting solution space of bi-level problem is usually no convex. In bi-level optimization the optimal solution corresponds to an extreme point of the follower reaction set which is an extreme point of convex space produced by the constraints of the leader and follower problem.

Bi-level optimization is a non convex optimization which makes its solution a difficult task. A lot of approaches have been proposed in the literature for the solution of the bi-level problem. The first category of algorithms is called extreme point algorithms. The most popular algorithm in this category is the K-th algorithm [2-3] and its extensions [4]. This type of algorithms have been used for linear bi-level optimization and the basic idea is that the global optimal solution of the bi-level program is attained at an extreme point of the space constructed by the constraints of the leader and follower program. Another type of algorithm is the transformation of the bi-level problem to one level problem using the Karush-Kuhn-Tucker optimality conditions [5]. Following this approach, the follower problem is replaced by the KKT conditions and appends the resultant system to the leader's problem giving rise to a non-linear optimization problem. After the transformation of the bi-level problem to a one level problem, the resulting optimization is solved using a standard nonlinear optimization approach. This method is used frequently in order to solve the bi-level problem although sometimes fails to obtain the global optimal solution. To overcome this issue an extended KKT method has been proposed [5]. Another group of algorithms is the penalty function algorithms which can be used in combination with the KKT method to solve non-linear bi-level problems. Finally the most recent new approach in order to solve any type of bi-level problem is the use of parametric global optimization [6] where the follower problem is solved as a parametric problem considering the follower's variables as parameters.

In this abstract we propose a new method based on duality theory and a decomposition approach in order to solve linear bi-level problems and mixed integer linear bi-level problems. Our algorithm can be considered as an extreme point algorithm where in each iteration we check if the optimal solution of the leaders' problem is also optimal for the follower problem. If not a valid cut is added excluding the previous solution and the algorithm goes on until the optimality condition is satisfied. Numerical example will be presented in order to illustrate the developed algorithm.

[1] Luis N. Vincente and Paul H. Calamai “Bilevel and multilevel programming : a bibliography review” Journal of global optimization 5:291-306, (1994).

[2] Wilfred Candler and Robert Townsley 1982 “A linear two-level programming problem” Computers & Operations Research, Vol. 9, Issue 1, 59-76 ().

[3] W. F. Bialas and M. H. Karwani 1984. “Two-Level Linear Programming” Management science 30, 1004- 1020.

[4] Chenggen Shi, Jie Lu, Guangquan Zhang 2005 “An extended Kth-best approach for linear bi-level programming” Applied Mathematics and Computation 164, 843–855.

[5] Chenggen Shi, Jie Lu, Guangquan Zhang 2005 “An extended Kuhn–Tucker approach for linear bi-level programming” Applied Mathematics and Computation 162, 51–63.

[6] Berc Rustem, V. Dua, P.M. Saraiva, E.N. Pistikopoulos ‘Parametric global optimisation for bilevel programming' Accepted for publication in Journal of Global Optimization, to appear – 2007.