A simple algorithm for the linear bilevel programming problem. (English) Zbl 0634.90075
Summary: An algorithm for the linear bilevel programming problem is offered which applies mainly the usual simplex method with an additional rule for including slack variables into the basis. The algorithm bases on the full description of the feasible set in a neighbourhood of a feasible point. This description is obtained using the theory of subgradients as well as the concept of “active constraints”. The result is an algorithm which seems to be easier to implement as other published procedures also based on the theorem that every solvable linear bilevel programming problem has a basic solution.
MSC:
| 90C31 | Sensitivity, stability, parametric optimization |
| 90C05 | Linear programming |
| 65K05 | Numerical mathematical programming methods |
References:
| [1] | Aiyoshi E., IEEE Trans. Syst. Man, and Cybern. SMC 11 pp 444– (1981) · doi:10.1109/TSMC.1981.4308712 |
| [2] | DOI: 10.1287/moor.8.2.260 · Zbl 0516.90061 · doi:10.1287/moor.8.2.260 |
| [3] | DOI: 10.1002/nav.3800310104 · Zbl 0537.90087 · doi:10.1002/nav.3800310104 |
| [4] | Bard J.F., IEEE Trans. Syst. Man, and Cybern. SMC 14 pp 711– (1984) |
| [5] | Beer K., Lösung gro{\(\beta\)}er linearer Optimierungsaufgaben (1977) |
| [6] | DOI: 10.1109/TAC.1982.1102880 · Zbl 0487.90005 · doi:10.1109/TAC.1982.1102880 |
| [7] | DOI: 10.1287/mnsc.30.8.1004 · Zbl 0559.90053 · doi:10.1287/mnsc.30.8.1004 |
| [8] | DOI: 10.1016/0305-0548(82)90006-5 · doi:10.1016/0305-0548(82)90006-5 |
| [9] | DOI: 10.1007/BF01593771 · Zbl 0378.90059 · doi:10.1007/BF01593771 |
| [10] | DOI: 10.1007/BF01580119 · Zbl 0276.90053 · doi:10.1007/BF01580119 |
| [11] | Krekó B., Lehrbueh uer linearen Optimieruiig (1973) |
| [12] | DOI: 10.1109/TAC.1984.1103503 · Zbl 0529.90104 · doi:10.1109/TAC.1984.1103503 |
| [13] | Rockafellar R.T., Convex analysis (1970) · Zbl 0193.18401 |
| [14] | DOI: 10.1287/opre.31.2.253 · Zbl 0506.90011 · doi:10.1287/opre.31.2.253 |
| [15] | Stackelberg H.V., Marktform una Gleichgewicht |
| [16] | DOI: 10.1080/00207728408926552 · Zbl 0542.90075 · doi:10.1080/00207728408926552 |
| [17] | Ignizio J.P., Linear programming in single- and multiple objective systems (1982) · Zbl 0484.90068 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
