A modified simplex approach for solving bilevel linear programming problems (Q1261406)

The author studies the bilevel linear programming problem (P): \(\max z= c_ 1' x_ 2+ c_ 2' x_ 2\) s.t. \(x_ 1\geq 0\), \(x_ 2\in S(x_ 1)= \{\arg\max d'x| Dx_ 1+ Ax\leq b\), \(x\geq 0\}\). A solution method for (P) was proposed by \textit{J. F. Bard} [IEEE Trans. Syst. Man Cybern. SMC- 14, 711-717 (1984; Zbl 0552.90081)] on making use of Kuhn-Tucker conditions and associating the problem \((\text{P}')\): \(\max z= c_ 1' x_ 1+ c_ 2' x_ 2- M(y' w+ x_ 2' v)\) s.t. \(Dx_ 1+ Ax_ 2+ Jw= b\), \(A' y- Jv= d\), \(x_ 1\), \(x_ 2\), \(y\), \(w\), \(v\geq 0\), where \(M\) is a large penalty parameter. The difficulty of specifying \(M\) may result in a local solution rather than a global solution. Therefore the author presents here an algorithm that is a modification of the simplex method determining a local solution and at the same time gives the highest value to the objective function of the problem \((\text{P}')\). The algorithm suggested is based on Beale's method which greatly simplifies here due to the special structure of the problem \((\text{P}')\). The author claims that the algorithm performs well on small test problems but reports no experience about its efficiency vis a vis other available algorithms on large scale problems.