双层规划若干问题的解法
|
摘要
本文主要研究双层规划若干问题的解法.全文共分四章,第一章是绪论,从第二章到第四章为论文主体部分.
在第二章,我们主要提出了边界搜索法、改进的边界搜索法、改进的K最好方法、内点法这几个解线性双层规划问题的新算法.其中边界搜索法、改进的边界搜索法以及改进的K最好方法都是让迭代点在约束域边界进行迭代,而内点法是根据内点思想让迭代点在可行域内部进行迭代.
在第三章,我们进一步考虑了几种特殊类型的双层规划问题,包括:多跟随者的双层规划问题,线性分数型的双层规划问题.这两类双层规划问题都是在实际问题中根据一般的双层规划问题演变而来的,有很强的应用价值.对于这两类问题我们也给出了他们的求解算法,这些算法都是基于第二章中介绍的方法而进行的改进.
在第四章中,我们讨论了关于双层规划的一些其它问题.一个是无解的双层规划问题.根据在实际问题中的需要,我们针对无解的双层规划问题提出了一种新的定义的解,并给出了求解的算法.另一个是关于极大极小值问题与双层规划之间关系的问题.将极大极小值问题转化为一类特殊的双层规划问题,并用解双层规划问题的方法来求解极大极小值问题.在本章最后我们还提出了作者以后关于双层规划问题的研究方向.
Bilevel programming problem is an important optimization problem in operational research. It can be applied in economy, engineering, management and military affairs which has an hierachical structure system. Von Stackelberg published a monograph[44] about game theory in unbalanced economic markets in 1934. In this monograph he built Von Stackelberg competition model named by his name first (also called double oligarch model). Von Stackelberg competition model describes two big competitor in finance. When one person makes a decision, he should considers both optimize his objective function and the other person's reflection. So he should changes his decision. Von Stackelberg competition model is a special model of bilevel programming problem. Because in World WarⅡNazification Germany implemented anti-competitive economic policy, it can not attract people's attention. After World WarⅡ,Von Stackelberg competition model caught the attention of researchers in game theory. In the mid-1970s, bilevel programming problem was introduced into optimization and made a rapid development. In recent years, bilevel programming problem attracts researchers' attention in many region (applied mathe-matic,operational research, management science, decision-making science, system science and economics), because of its comprehensive application.
Bilevel programming problem is an optimization problem whose constraint is another optimization problem. It can be showed in the following form:where x∈X (?) R~n,y∈Y (?) R~m,F,f:X×Y→R~1,G:X×Y→R~p,g:X×Y→R~q.
In this paper we consider the algorithms of some bilevel programming problem, and mainly obtain the following results:
1,We present boundary search method for solving linear bilevel programming problem.
Firstly, we solve the following problem (2)by the following boundary search method:
Step 1 Let i←1.Using the simplex method, we can obtain the optimal solution x_1=(x_1~1,x_1~2,…,x_1~n)~T from problem (2.1.3).Go to step 2.
Step 2 Let current iterative point be x_2=(x_2~1,x_2~2,…,x_2~n)~T.Using the simplex method, we can obtain the optimal solution x'_2 of problem (1.2.3). If x_2=x'_2,x_2 is the solution of problem (2). Otherwise, go to step 3.
Step 3 Let current iterative point be x_3=(x_3~1,x_3~2,…,x_3~n)~T.Assume x_3 satisfy p constraint conditions, and let they are first p. Let d = (d_1,d_2,…,d_n)~T be search direction. Choose min{p,n-1} constraint conditions from p constraint conditions arbitrarily, then d is the solution of the following equations:the step length of search direction is: For the point x_3,search direction d and the step length t,x_3+td is a adjacent extreme point of x_3.We can obtain other extreme points of x_3 like this. Check whether there exists a point both satisfy the lower-level optimality condition and in the feasible region.If not exist, choose the point which minimize the upper-level objective function as new iterative point, go to step 4. Otherwise, choose the point which maximize the upper-level objective function as new iterative point, go to step 5.
Step 4 Let current iterative point be x_4={x_4~1,x_4~2,x_4~n)~T.Choose n-1 constraint conditions from p constraint conditions arbitrarily that x_4 satisfy:and let them take "=". From these n-1 equations and the new added constraintwe can obtain some new boundary points. Check whether there exists a point both satisfy the lower-level optimality condition and in the feasible region. If exist, choose it as new iterative point, go to step 3. Otherwise, x_4 is still iterative point, go to step 3.
Step 5 Let current iterative point be x_5=(x_5~1,x_5~2,?x_5~n)~T.Choose n-1 constraint conditions from p constraint conditions arbitrarily that x_5 satisfy: and let them take "=".From these n-1 equations and the new added constraintwe can obtain some new boundary points. Check whether there exists a point both satisfy the lower-level optimality condition and in the feasible region. If exist, choose it as new iterative point, go to step 3. Otherwise, x_5 is the optimal solution of problem (2).
Then choose the optimal solution of problem (2) as initial iterative point to solve the linear bilevel programming problem (3):
Boundary search method for solving linear bilevel programming problemis presented in the following:
Step 1 Let F =+∞is upper-level objective funciton value, T=(?) is the set of iterative points that we have known, W=(?) is the set of feasible extreme points. By the method in [27] and [28], we can obtiain the solution x_1 of problem (2). Check x\ whether satisfy upper-level constraint conditions. If satisfy, then the solution x_1 of problem (2) is also the problem (3)'s solution. If not satisfy, choose x_1 as iterative point, update T = T∪{x_1},W=(?),F=c~2x_1,go to step 2.
Step 2 Let x_2 ={x_2~1,x_2~2,…,x_2~n)~T is current iterative point. The search direction isAssume x_2 satisfy p constraint conditions, and let they are first p. Choose min{p,n-1} constraint conditions from p constraint conditions arbitrarily, and consider the following problem:
We can obtain the search direction d. Because the choosen are different,we can obtain q search directions and denote asTakeinto all the constraint conditions to solve the step length max{t} respectively.So we can obtain q adjacent extreme points of x_2.If there exists a point both satisfy the lower-level optimality condition and in the feasible region, go to step 3. Otherwise, T = T∪{x_2},F=c~2x_2,W=(W∪W')\T, (W' is the set of x_2's adjacent extreme points which satisfy lower-level optimality condition). Choose the point which maximize the upper-level objective function from W as new iterative point, go to step 2.
Step 3 Let x_3 = (x_3~1,x_3~2,?x_3~n)~T is current iterative point. Denote the points which both satisfy the lower-level optimality condition and in the upper-level constraint conditions in step 2 as x_(j')(j' =1,2,?p'),the corresponding search direction are d_(j').UpdateTake x'_(j')=x_(j')-d_(j')t (t≥0) into all the constraint conditions to solve the step length max{t} respectively. So we can obtain x'_(j')(j'=1,2,…,p'). Then solve the following problem:Let (?) is the solution of problem (4).If c~2(?)>F,update F=c~2(?).Otherwise,not change F. Choose the point which maximize the upper-level objective function from W and denote as x'.If F > c~2x',then x~* which is corresponding to F is the solution of problem (3).Otherwise, choose x' as iterative point, go to step 2.
2,We present Kth-best approach for solving linear bilevel programming problem which is in the following:Step 1 Let x_0=(x_0~1,x_0~2,…,x_0~n)~T be a feasible point arbitrarily.Step 2 Fix (x_0~(s+1),…,x_0~n) in the lower-level problem, then the problem is transformed to: Using the simplex method, we obtain the solution of the problemwhereand make it is new iterative point. For x_1 and optimal search direction c~2=(c~(21),c~(22),?c~(2n)),we should guarantee that the new iterative point is in the feasible region, namely:If t≠0, we can obtain a new iterative point (x_1 + (c~2)~Tt),update x_0 = (x_1 + (c~2)~Tt),repeat step 2. Otherwise, go to step 3.
Step 3 Let current iterative point beAssume x_2 makes i constraint conditions take "=",let they are first i constraint conditions. Then:
(i) If i≤n-1,d~* is the solution of the following problem:We can obtain the suboptimal search direction d~*,go to step 4.
(ii) If i≥n,we solve the following problem:where constraint conditions are n-1 constraint conditions from i constraint conditions arbitrarily. So we can obtain p solution, denote as d_j (j = 1,2,…,p).Go to step 5.
Step 4 For the current iterative point and suboptimal search directionwe should guarantee that the new iterative point is in the feasible region, namely:We can obtain a new iterative point x_3=(x~2+(d~*)~Tt).Take (x_3~(s+1),?x_3~n) into lower-level problem, it is transformed to: Using the simplex method, we can obtain a new iterative point, denote aswhereGo to step 3.
Step 5 Let the current iterative point be x_5 = (x_5~1,x_5~2,?x_5~n)~T.d_j(j = 1,2,…,p) is the suboptimal search direction. Takeinto the lower-level constraint conditions to solve the step length max{t} respectively. If there exist t > 0 such that the new iterative point satisfy lower-level optimality condition, then choose the point which maximize the upper-level objective function as new iterative point, go to step 3. Otherwise,x_5 is still iterative point, go to step 6.
Step 6 Let the current iterative point be x_6 = (x_6~1,x_6~2,…,x_6~n)~T.Choose n-1 constraint conditions from m constraint conditions arbitrarily that x_6 satisfy: and let them take "=".From these n-1 equations and the new added constraintwe can obtain some new boundary points. Check whether there exists a point both satisfy the lower-level optimality condition and in the feasible region. If exist, choose it as new iterative point, go to step 3. Otherwise, x_6 is the optimal solution of problem (3).
3,We present interior point method for solving linear bilevel programming problem which is in the following:
Step 1 Let x_1 be initial iterative point which is in feasible region. Let the upper and lower boundary of iterative direction is d_u=c~2,d_ι=c~1.Choose d_1=d_u=c~2 as initial iterative direction. Take x_1 + d_1t into constraint conditions and obtain step length t and x'_1 =x_1+ d_1t.If x'_1 satisfy lower-level optimality condition, then use boundary search method or extend Kth-best approach. If x'_1 do not satisfy lower-level optimality condition, go to step 2.
Step 2 Let the current iterative point be x_2,update iterative direction d_2=(?)(d_u+d_ι).Take x_2+d_2t into constraint conditions and obtain step length t and x'_2=x_2+d_2t.If x'_2 do not satisfy lower-level optimality condition, iterative point do not change, update d_u=d_2,d_ι=d_ι.Repeat step 2. If x'_2 satisfy lower-level optimality condition, the new iterative point is x_3 = x_2 + (?)d_2t,update d_u= d_u,d_ι= d_2.If step length t >ε(εis prior fixed), repeat step 2. Otherwise, go to step 3.
Step 3 Let the current iterative point be x_3.Add a new plane c~2x= c~2x_3.Choose n-1 constraint conditions arbitrarily from the constraint conditions that x_3 satisfy. Prom these n-1 equations and the new plane, we can obtain some new boundary points. Check whether there exists a point satisfy the lower-level optimality condition. If there do not exist,x_3 is the optimal solution of the problem (3). If there exist, choose one and denote as x'_3,update d_u= d_u,d_ι=x'_3-x_3,and x_3 is still iterative point. Go to step 2.
4,We also consider the following two problem, such as, multi-followers bilevel programming problem, fractional bilevel programming problems. These two problem are all derived from normal bilevel programming problem in practical problem and have important application.We give the method for solving these two problem which are based on the method above.
5,We give a new definition of the optimal solution for no solution bilevel programming problem.Definition 6.0.1 We call the optimal solution of problem (5) is the feasible optimal solution of problem (1). where u_(max) and u_(min) are objective function value of problem (6) and (7).
6, We transform max-min problems to a special type bilevel programming problem and give the following theorem:Theorem 6.0.1 max-min problem (8)is equivalent to the bilevel programming problem (9) And we also solve max-min problems via solving this bilevel programming problem.
在第二章,我们主要提出了边界搜索法、改进的边界搜索法、改进的K最好方法、内点法这几个解线性双层规划问题的新算法.其中边界搜索法、改进的边界搜索法以及改进的K最好方法都是让迭代点在约束域边界进行迭代,而内点法是根据内点思想让迭代点在可行域内部进行迭代.
在第三章,我们进一步考虑了几种特殊类型的双层规划问题,包括:多跟随者的双层规划问题,线性分数型的双层规划问题.这两类双层规划问题都是在实际问题中根据一般的双层规划问题演变而来的,有很强的应用价值.对于这两类问题我们也给出了他们的求解算法,这些算法都是基于第二章中介绍的方法而进行的改进.
在第四章中,我们讨论了关于双层规划的一些其它问题.一个是无解的双层规划问题.根据在实际问题中的需要,我们针对无解的双层规划问题提出了一种新的定义的解,并给出了求解的算法.另一个是关于极大极小值问题与双层规划之间关系的问题.将极大极小值问题转化为一类特殊的双层规划问题,并用解双层规划问题的方法来求解极大极小值问题.在本章最后我们还提出了作者以后关于双层规划问题的研究方向.
Bilevel programming problem is an important optimization problem in operational research. It can be applied in economy, engineering, management and military affairs which has an hierachical structure system. Von Stackelberg published a monograph[44] about game theory in unbalanced economic markets in 1934. In this monograph he built Von Stackelberg competition model named by his name first (also called double oligarch model). Von Stackelberg competition model describes two big competitor in finance. When one person makes a decision, he should considers both optimize his objective function and the other person's reflection. So he should changes his decision. Von Stackelberg competition model is a special model of bilevel programming problem. Because in World WarⅡNazification Germany implemented anti-competitive economic policy, it can not attract people's attention. After World WarⅡ,Von Stackelberg competition model caught the attention of researchers in game theory. In the mid-1970s, bilevel programming problem was introduced into optimization and made a rapid development. In recent years, bilevel programming problem attracts researchers' attention in many region (applied mathe-matic,operational research, management science, decision-making science, system science and economics), because of its comprehensive application.
Bilevel programming problem is an optimization problem whose constraint is another optimization problem. It can be showed in the following form:where x∈X (?) R~n,y∈Y (?) R~m,F,f:X×Y→R~1,G:X×Y→R~p,g:X×Y→R~q.
In this paper we consider the algorithms of some bilevel programming problem, and mainly obtain the following results:
1,We present boundary search method for solving linear bilevel programming problem.
Firstly, we solve the following problem (2)by the following boundary search method:
Step 1 Let i←1.Using the simplex method, we can obtain the optimal solution x_1=(x_1~1,x_1~2,…,x_1~n)~T from problem (2.1.3).Go to step 2.
Step 2 Let current iterative point be x_2=(x_2~1,x_2~2,…,x_2~n)~T.Using the simplex method, we can obtain the optimal solution x'_2 of problem (1.2.3). If x_2=x'_2,x_2 is the solution of problem (2). Otherwise, go to step 3.
Step 3 Let current iterative point be x_3=(x_3~1,x_3~2,…,x_3~n)~T.Assume x_3 satisfy p constraint conditions, and let they are first p. Let d = (d_1,d_2,…,d_n)~T be search direction. Choose min{p,n-1} constraint conditions from p constraint conditions arbitrarily, then d is the solution of the following equations:the step length of search direction is: For the point x_3,search direction d and the step length t,x_3+td is a adjacent extreme point of x_3.We can obtain other extreme points of x_3 like this. Check whether there exists a point both satisfy the lower-level optimality condition and in the feasible region.If not exist, choose the point which minimize the upper-level objective function as new iterative point, go to step 4. Otherwise, choose the point which maximize the upper-level objective function as new iterative point, go to step 5.
Step 4 Let current iterative point be x_4={x_4~1,x_4~2,x_4~n)~T.Choose n-1 constraint conditions from p constraint conditions arbitrarily that x_4 satisfy:and let them take "=". From these n-1 equations and the new added constraintwe can obtain some new boundary points. Check whether there exists a point both satisfy the lower-level optimality condition and in the feasible region. If exist, choose it as new iterative point, go to step 3. Otherwise, x_4 is still iterative point, go to step 3.
Step 5 Let current iterative point be x_5=(x_5~1,x_5~2,?x_5~n)~T.Choose n-1 constraint conditions from p constraint conditions arbitrarily that x_5 satisfy: and let them take "=".From these n-1 equations and the new added constraintwe can obtain some new boundary points. Check whether there exists a point both satisfy the lower-level optimality condition and in the feasible region. If exist, choose it as new iterative point, go to step 3. Otherwise, x_5 is the optimal solution of problem (2).
Then choose the optimal solution of problem (2) as initial iterative point to solve the linear bilevel programming problem (3):
Boundary search method for solving linear bilevel programming problemis presented in the following:
Step 1 Let F =+∞is upper-level objective funciton value, T=(?) is the set of iterative points that we have known, W=(?) is the set of feasible extreme points. By the method in [27] and [28], we can obtiain the solution x_1 of problem (2). Check x\ whether satisfy upper-level constraint conditions. If satisfy, then the solution x_1 of problem (2) is also the problem (3)'s solution. If not satisfy, choose x_1 as iterative point, update T = T∪{x_1},W=(?),F=c~2x_1,go to step 2.
Step 2 Let x_2 ={x_2~1,x_2~2,…,x_2~n)~T is current iterative point. The search direction isAssume x_2 satisfy p constraint conditions, and let they are first p. Choose min{p,n-1} constraint conditions from p constraint conditions arbitrarily, and consider the following problem:
We can obtain the search direction d. Because the choosen are different,we can obtain q search directions and denote asTakeinto all the constraint conditions to solve the step length max{t} respectively.So we can obtain q adjacent extreme points of x_2.If there exists a point both satisfy the lower-level optimality condition and in the feasible region, go to step 3. Otherwise, T = T∪{x_2},F=c~2x_2,W=(W∪W')\T, (W' is the set of x_2's adjacent extreme points which satisfy lower-level optimality condition). Choose the point which maximize the upper-level objective function from W as new iterative point, go to step 2.
Step 3 Let x_3 = (x_3~1,x_3~2,?x_3~n)~T is current iterative point. Denote the points which both satisfy the lower-level optimality condition and in the upper-level constraint conditions in step 2 as x_(j')(j' =1,2,?p'),the corresponding search direction are d_(j').UpdateTake x'_(j')=x_(j')-d_(j')t (t≥0) into all the constraint conditions to solve the step length max{t} respectively. So we can obtain x'_(j')(j'=1,2,…,p'). Then solve the following problem:Let (?) is the solution of problem (4).If c~2(?)>F,update F=c~2(?).Otherwise,not change F. Choose the point which maximize the upper-level objective function from W and denote as x'.If F > c~2x',then x~* which is corresponding to F is the solution of problem (3).Otherwise, choose x' as iterative point, go to step 2.
2,We present Kth-best approach for solving linear bilevel programming problem which is in the following:Step 1 Let x_0=(x_0~1,x_0~2,…,x_0~n)~T be a feasible point arbitrarily.Step 2 Fix (x_0~(s+1),…,x_0~n) in the lower-level problem, then the problem is transformed to: Using the simplex method, we obtain the solution of the problemwhereand make it is new iterative point. For x_1 and optimal search direction c~2=(c~(21),c~(22),?c~(2n)),we should guarantee that the new iterative point is in the feasible region, namely:If t≠0, we can obtain a new iterative point (x_1 + (c~2)~Tt),update x_0 = (x_1 + (c~2)~Tt),repeat step 2. Otherwise, go to step 3.
Step 3 Let current iterative point beAssume x_2 makes i constraint conditions take "=",let they are first i constraint conditions. Then:
(i) If i≤n-1,d~* is the solution of the following problem:We can obtain the suboptimal search direction d~*,go to step 4.
(ii) If i≥n,we solve the following problem:where constraint conditions are n-1 constraint conditions from i constraint conditions arbitrarily. So we can obtain p solution, denote as d_j (j = 1,2,…,p).Go to step 5.
Step 4 For the current iterative point and suboptimal search directionwe should guarantee that the new iterative point is in the feasible region, namely:We can obtain a new iterative point x_3=(x~2+(d~*)~Tt).Take (x_3~(s+1),?x_3~n) into lower-level problem, it is transformed to: Using the simplex method, we can obtain a new iterative point, denote aswhereGo to step 3.
Step 5 Let the current iterative point be x_5 = (x_5~1,x_5~2,?x_5~n)~T.d_j(j = 1,2,…,p) is the suboptimal search direction. Takeinto the lower-level constraint conditions to solve the step length max{t} respectively. If there exist t > 0 such that the new iterative point satisfy lower-level optimality condition, then choose the point which maximize the upper-level objective function as new iterative point, go to step 3. Otherwise,x_5 is still iterative point, go to step 6.
Step 6 Let the current iterative point be x_6 = (x_6~1,x_6~2,…,x_6~n)~T.Choose n-1 constraint conditions from m constraint conditions arbitrarily that x_6 satisfy: and let them take "=".From these n-1 equations and the new added constraintwe can obtain some new boundary points. Check whether there exists a point both satisfy the lower-level optimality condition and in the feasible region. If exist, choose it as new iterative point, go to step 3. Otherwise, x_6 is the optimal solution of problem (3).
3,We present interior point method for solving linear bilevel programming problem which is in the following:
Step 1 Let x_1 be initial iterative point which is in feasible region. Let the upper and lower boundary of iterative direction is d_u=c~2,d_ι=c~1.Choose d_1=d_u=c~2 as initial iterative direction. Take x_1 + d_1t into constraint conditions and obtain step length t and x'_1 =x_1+ d_1t.If x'_1 satisfy lower-level optimality condition, then use boundary search method or extend Kth-best approach. If x'_1 do not satisfy lower-level optimality condition, go to step 2.
Step 2 Let the current iterative point be x_2,update iterative direction d_2=(?)(d_u+d_ι).Take x_2+d_2t into constraint conditions and obtain step length t and x'_2=x_2+d_2t.If x'_2 do not satisfy lower-level optimality condition, iterative point do not change, update d_u=d_2,d_ι=d_ι.Repeat step 2. If x'_2 satisfy lower-level optimality condition, the new iterative point is x_3 = x_2 + (?)d_2t,update d_u= d_u,d_ι= d_2.If step length t >ε(εis prior fixed), repeat step 2. Otherwise, go to step 3.
Step 3 Let the current iterative point be x_3.Add a new plane c~2x= c~2x_3.Choose n-1 constraint conditions arbitrarily from the constraint conditions that x_3 satisfy. Prom these n-1 equations and the new plane, we can obtain some new boundary points. Check whether there exists a point satisfy the lower-level optimality condition. If there do not exist,x_3 is the optimal solution of the problem (3). If there exist, choose one and denote as x'_3,update d_u= d_u,d_ι=x'_3-x_3,and x_3 is still iterative point. Go to step 2.
4,We also consider the following two problem, such as, multi-followers bilevel programming problem, fractional bilevel programming problems. These two problem are all derived from normal bilevel programming problem in practical problem and have important application.We give the method for solving these two problem which are based on the method above.
5,We give a new definition of the optimal solution for no solution bilevel programming problem.Definition 6.0.1 We call the optimal solution of problem (5) is the feasible optimal solution of problem (1). where u_(max) and u_(min) are objective function value of problem (6) and (7).
6, We transform max-min problems to a special type bilevel programming problem and give the following theorem:Theorem 6.0.1 max-min problem (8)is equivalent to the bilevel programming problem (9) And we also solve max-min problems via solving this bilevel programming problem.
引文
[1] Aiyoshi E, Shimizu K. Hierarchical decentralized systems and its new solution by a barrier method. IEEE Transactions on Systems, Man, and Cybernetics 1981, 11: 444-449.
[2] Amouzegar M, Moshirvaziri K. A penalty method for linear bilevel programming problems,In Multilevel Optimization: Algorithms and Applications. A Migdalas, PM Pardalos and P V(a|¨)rbrand (eds.), Dordrecht: Kluwer Academic Publishers, 1998.
[3] An L T H, Pham D T, Muu L D. Exact penalty in D.C.programming. Vietnam Journal of Mathematics, 1999, 27: 161-178.
[4] Anandalingam G , White D J. A solution method for the linear static Stackelberg problem using penalty functions. IEEE Transactions on Automatic Control, 1990, 35(10): 1170-1173.
[5] Audet C, Haddad J, Savard G.,A note on the definition of a linear bilevel programming solution. Applied Mathematics and Computation, 2006, 181 (1): 351-355.
[6] Bard J, Palk J.An explicit solution to the multi-level programming problem. Computers and Operations Research, 1982, 9: 77-100.
[7] Bard J. An investigation of the linear three level programming problem. IEEE Transactions on Systems, Man, and Cybernetics, 1984, 14: 711-717.
[8] Bard J. Practical Bilevel Optimization: Algorithms and Applications. Kluwer Academic Publishers, USA, 1998.
[9] Bard J, Moore J T. A branch and bound algorithm for the bilevel programming problem.SIAM Journal on Scientific and Statistical Computing, 1990, 11: 281-292.
[10] Bard J. Convex two-level optimization. Mathematical Programming, 1988, 40: 15-27.
[11] Bard J. An algorithm for solving the general bilevel programming problem. Mathematics of Operations Research, 1983 8: 260-272.
[12] Bard J. An efficient algorithm for a linear two-stage optimization problem. Operations Research July-August, 1983, 670-684.
[13] Basar T, Srikant R. A Stackelberg network game with a large number of followers. Journal of Optimization Theory and Applications, 2002, 115(3): 479-490.
[14] Ben-Ayed O.Bilevel linear programming. Computer and Operations Research, 1993, 20:485-509.
[15] Bialas W, Karwan M. Multilevel linear programming. Technical Report 78-1,Operations Research Program, State University of New York at Buffalo, 1978.
[16] Bialas W, Karwan M, Shaw J., A parametric complementary pivot approach for two-levellinear programming. Technical Report 80-2, Operations Research Program, State University of New York at Buffalo, 1978.
[17] Bialas W, Karwan M. Two-level linear programming. Management Science,1984, 30: 1004-1020.
[18] Brotcorne L, Labb(?) M, Marcotte P, Savard G. A bilevel model and solution algorithm for a freight tariff-setting problem. Transportation Science, 2000, 34(3): 289-302.
[19] Calvete H I, Gal(?) M C. Linear bilevel multi-follower programming with independent followers. Journal of Global Optimization, 2007, 39: 409-417.
[20] Calvete H I, Gal(?) M C. Solving linear fractional bilevel programs. Operations Research Letters , 2004, 32: 143-151.
[21] Calvete H I, Gal(?) M C. On the quasiconcave bilevel programming problem. Journal of Optimization Theory and Applications, 1998, 98(3): 613-622.
[22] Calvete H I, Gal(?) M C. Bilevel multiplicative problems: A penalty approach to optimality and a cutting plane based algorithm. Journal of Computational and Applied Mathematics,2008, 218: 259-269.
[23] Campelo M, Dantas S, Scheimberg S. A note on a penalty function approach for solving bilevel linear programs. Journal of Global Optimization, 2000 16: 245-255.
[24] Candler W, Townsley R. A linear two-level programming problem. Computers and Operations Research, 1982 9: 59-76.
[25] Dempe S. Foundations of Bilevel Programming. Dordrecht, Boston, London: Kluwer Academic Publishers, 2002.
[26] Dempe S. Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints. Optimization, 2003, 52: 333-359.
[27] 邓键，黄庆道，马明娟，张瑶．改进的k最好方法解无上层约束的线性双层规划问题．吉林大学学报(理学版)，2008，46(6)：1031-1036．
[28] DENG Jian, HUANG Qing-dao and MA Ming-juan. An Optimal Method for Solving the Linear Bilevel Programming Problem with No Upper-level Constraint. NORTH-EAST.MATH.J, 2008, 24(5): 433-446.
[29] Dewez S. On the toll setting problem. Ph.D. dissertation, Universit(?) Libre de Bruxelles.
[30] Ehtamo H, Raivio T. On applied nonlinear and bilevel programming for pursuit-evasion games. J. of Optimization Theory and Applications, 2001,108(1):65-96.
[31] Fortuny-Amat J, McCarl B. A representation and economic interpretation of a two-level programming problem. Journal of the Operational Research Society, 1981, 32: 783-792.
[32] Hansen P, Jaumard B, Savard G. New branch-and-bound rules for linear bilevel programming.SIAM Journal on Scientific and Statistical Computing, 1982, 13: 1194-1217.
[33] Ishizuka Y, Aiyoshi E. Double penalty method for bilevel optimization problems. Annals of Operations Research, 1992, 34, 73-88.
[34] Judice J, Faustino A M. A sequencial LCP method for bilevel linear programming. Annals of Operations Research, 1992, 34: 89-106.
[35] Labb(?) M , Marcotte P , Savard G. A bilevel model of taxation and its application to optimal highway pricing. Management Science, 1998, 44: 1608-1622.
[36] Lu J, Shi C, Zhang G. On bilevel multi-follower decision making: General framework and solutions. Information Sciences, 2006, 176: 1607-1627.
[37] Marcotte P, Savard G, Semet F. A bilevel programming approach to the travelling salesman problem. Operations Research Letters, 2004, 32: 240-248.
[38] Migdalas A , Pardalos P, V(a|¨)rbrand P , (eds.). Multilevel Optimization: Algorithms and Applications. Kluwer Academic Publishers, Dordrecht.
[39] Muu L D. On the construction of initial polyhedral convex set for optimization problem over the efficient set and bilevel linear program. Vietnam Journal of Mathematics, 2000,28: 177-182.
[40] Quy N V, Muu L D. On penalty function method for a class of nonconvex constrained optimization problems. Vietnam Journal of Mathematics, 2001, 29: 235-256.
[55] Zhang J Z, Zhu D T. A bilevel programming method for pipe network optimization. SIAM Journal on Optimization, 1996, 6(3): 838-857.
[2] Amouzegar M, Moshirvaziri K. A penalty method for linear bilevel programming problems,In Multilevel Optimization: Algorithms and Applications. A Migdalas, PM Pardalos and P V(a|¨)rbrand (eds.), Dordrecht: Kluwer Academic Publishers, 1998.
[3] An L T H, Pham D T, Muu L D. Exact penalty in D.C.programming. Vietnam Journal of Mathematics, 1999, 27: 161-178.
[4] Anandalingam G , White D J. A solution method for the linear static Stackelberg problem using penalty functions. IEEE Transactions on Automatic Control, 1990, 35(10): 1170-1173.
[5] Audet C, Haddad J, Savard G.,A note on the definition of a linear bilevel programming solution. Applied Mathematics and Computation, 2006, 181 (1): 351-355.
[6] Bard J, Palk J.An explicit solution to the multi-level programming problem. Computers and Operations Research, 1982, 9: 77-100.
[7] Bard J. An investigation of the linear three level programming problem. IEEE Transactions on Systems, Man, and Cybernetics, 1984, 14: 711-717.
[8] Bard J. Practical Bilevel Optimization: Algorithms and Applications. Kluwer Academic Publishers, USA, 1998.
[9] Bard J, Moore J T. A branch and bound algorithm for the bilevel programming problem.SIAM Journal on Scientific and Statistical Computing, 1990, 11: 281-292.
[10] Bard J. Convex two-level optimization. Mathematical Programming, 1988, 40: 15-27.
[11] Bard J. An algorithm for solving the general bilevel programming problem. Mathematics of Operations Research, 1983 8: 260-272.
[12] Bard J. An efficient algorithm for a linear two-stage optimization problem. Operations Research July-August, 1983, 670-684.
[13] Basar T, Srikant R. A Stackelberg network game with a large number of followers. Journal of Optimization Theory and Applications, 2002, 115(3): 479-490.
[14] Ben-Ayed O.Bilevel linear programming. Computer and Operations Research, 1993, 20:485-509.
[15] Bialas W, Karwan M. Multilevel linear programming. Technical Report 78-1,Operations Research Program, State University of New York at Buffalo, 1978.
[16] Bialas W, Karwan M, Shaw J., A parametric complementary pivot approach for two-levellinear programming. Technical Report 80-2, Operations Research Program, State University of New York at Buffalo, 1978.
[17] Bialas W, Karwan M. Two-level linear programming. Management Science,1984, 30: 1004-1020.
[18] Brotcorne L, Labb(?) M, Marcotte P, Savard G. A bilevel model and solution algorithm for a freight tariff-setting problem. Transportation Science, 2000, 34(3): 289-302.
[19] Calvete H I, Gal(?) M C. Linear bilevel multi-follower programming with independent followers. Journal of Global Optimization, 2007, 39: 409-417.
[20] Calvete H I, Gal(?) M C. Solving linear fractional bilevel programs. Operations Research Letters , 2004, 32: 143-151.
[21] Calvete H I, Gal(?) M C. On the quasiconcave bilevel programming problem. Journal of Optimization Theory and Applications, 1998, 98(3): 613-622.
[22] Calvete H I, Gal(?) M C. Bilevel multiplicative problems: A penalty approach to optimality and a cutting plane based algorithm. Journal of Computational and Applied Mathematics,2008, 218: 259-269.
[23] Campelo M, Dantas S, Scheimberg S. A note on a penalty function approach for solving bilevel linear programs. Journal of Global Optimization, 2000 16: 245-255.
[24] Candler W, Townsley R. A linear two-level programming problem. Computers and Operations Research, 1982 9: 59-76.
[25] Dempe S. Foundations of Bilevel Programming. Dordrecht, Boston, London: Kluwer Academic Publishers, 2002.
[26] Dempe S. Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints. Optimization, 2003, 52: 333-359.
[27] 邓键，黄庆道，马明娟，张瑶．改进的k最好方法解无上层约束的线性双层规划问题．吉林大学学报(理学版)，2008，46(6)：1031-1036．
[28] DENG Jian, HUANG Qing-dao and MA Ming-juan. An Optimal Method for Solving the Linear Bilevel Programming Problem with No Upper-level Constraint. NORTH-EAST.MATH.J, 2008, 24(5): 433-446.
[29] Dewez S. On the toll setting problem. Ph.D. dissertation, Universit(?) Libre de Bruxelles.
[30] Ehtamo H, Raivio T. On applied nonlinear and bilevel programming for pursuit-evasion games. J. of Optimization Theory and Applications, 2001,108(1):65-96.
[31] Fortuny-Amat J, McCarl B. A representation and economic interpretation of a two-level programming problem. Journal of the Operational Research Society, 1981, 32: 783-792.
[32] Hansen P, Jaumard B, Savard G. New branch-and-bound rules for linear bilevel programming.SIAM Journal on Scientific and Statistical Computing, 1982, 13: 1194-1217.
[33] Ishizuka Y, Aiyoshi E. Double penalty method for bilevel optimization problems. Annals of Operations Research, 1992, 34, 73-88.
[34] Judice J, Faustino A M. A sequencial LCP method for bilevel linear programming. Annals of Operations Research, 1992, 34: 89-106.
[35] Labb(?) M , Marcotte P , Savard G. A bilevel model of taxation and its application to optimal highway pricing. Management Science, 1998, 44: 1608-1622.
[36] Lu J, Shi C, Zhang G. On bilevel multi-follower decision making: General framework and solutions. Information Sciences, 2006, 176: 1607-1627.
[37] Marcotte P, Savard G, Semet F. A bilevel programming approach to the travelling salesman problem. Operations Research Letters, 2004, 32: 240-248.
[38] Migdalas A , Pardalos P, V(a|¨)rbrand P , (eds.). Multilevel Optimization: Algorithms and Applications. Kluwer Academic Publishers, Dordrecht.
[39] Muu L D. On the construction of initial polyhedral convex set for optimization problem over the efficient set and bilevel linear program. Vietnam Journal of Mathematics, 2000,28: 177-182.
[40] Quy N V, Muu L D. On penalty function method for a class of nonconvex constrained optimization problems. Vietnam Journal of Mathematics, 2001, 29: 235-256.
[55] Zhang J Z, Zhu D T. A bilevel programming method for pipe network optimization. SIAM Journal on Optimization, 1996, 6(3): 838-857.