Abstract
A special linear, three-level optimization problem is considered where the reaction of the third-level decision maker influences the objective functions of both decision makers on the first and the second level via its optimal objective function value. For this problem, existence of an optimal solution as well as its computation are investigated.
Similar content being viewed by others
References
Alizadeh, S.M., Marcotte, P., Savard, G.: Two-stage stochastic bilevel programming over a transportation network. Transp. Res. Part B: Methodol. 58, 92–105 (2013)
Aussel, D., Bendotti, P., Pištěk, M.: Nash equilibrium in a pay-as-bid electricity market: part 1— existence and characterization. Optimization 66, 1013–1025 (2017)
Aussel, D., Bendotti, P., Pištěk, M.: Nash equilibrium in a pay-as-bid electricity market part 2—best response of a producer. Optimization 66, 1027–1053 (2017)
Bank, B., Guddat, J., Klatte, D., Kummer, B., Tammer, K.: Non-linear Parametric Optimization. Birkhäuser Verlag, Basel (1983)
Bard, J.F.: Practical Bilevel Optimization: Algorithms and Applications. Kluwer, Dordrecht (1998)
Camacho-Vallejo, J.-F., González-Rodríguez, E., Almaguer, F.-J., González-Ramírez, R.G.: A bi-level optimization model for aid distribution after the occurrence of a disaster. J. Clean. Prod. 105, 134–145 (2014)
Dempe, S.: Foundations of Bilevel Programming. Kluwer, Dordrecht (2002)
Dempe, S.: Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints. Optimization 52, 333–359 (2003)
Dempe, S., Dutta, J.: Is bilevel programming a special case of a mathematical program with complementarity constraints? Math. Program. 131, 37–48 (2012)
Dempe, S., Franke, S.: Solution of bilevel optimization problems using the KKT approach. Optimization 68, 1471–1489 (2019)
Dempe, S., Kalashnikov, V., Pérez-Valdés, G.A., Kalashnykova, N.: Bilevel Programming Problems: Theory, Algorithms and Application to Energy Networks. Springer, Berlin (2015)
Florensa, C., Garcia-Herreros, P., Misra, P., Arslan, E., Mehta, S., Grossmann, I.E.: Capacity planning with competitive decision-makers: trilevel MILP formulation, degeneracy, and solution approaches. Eur. J. Oper. Res. 262, 449–463 (2017)
Fourer, R., Gay, D.M., Kernighan, B.W.: AMPL: A Modeling Language for Mathematical Programming. Scientific Press, San Francisco (1993)
Hoffman, A.J.: On approximate solutions of systems of linear inequalities. Res. Nat. Bur. Stand. 49, 263–265 (1952)
Hoheisel, T., Kanzow, C., Schwartz, A.: Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints. Math. Program. 137(1–2), 257–288 (2013)
Kochetov, Y., Kochetova, N., Plyasunov, A.: A matheuristic for the leader-follower facility location and design problem. In: Proceedings of the 10th Metaheuristics International Conference (MIC 2013), vol. 32. Citeseer (2013)
Mersha, A.G.: Solution methods for bilevel programming problems, Ph.D. thesis, TU Bergakademie Freiberg (2008)
Mersha, A.G., Dempe, S.: Feasible direction method for bilevel programming problem. Optimization 61(4–6), 597–616 (2012)
Outrata, J., Kočvara, M., Zowe, J.: Nonsmooth Approach to Optimization Problems with Equilibrium Constraints. Kluwer, Dordrecht (1998)
Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)
Rog, R.: Solution algorithms for the KKT-transformation of bilevel optimization problems, Master’s thesis, TU Bergakademie Freiberg, Fakultät für Mathematik und Informatik, 2017, in German language. Title: Lösungsalgorithmen für die KKT-Transformation von Zwei-Ebenen-Optimierungsaufgaben (2017)
Sadatrasou, S.M., Gholamian, M.R., Shahanaghi, K.: An application of data mining classification and bi-level programming for optimal credit allocation. Decision Sci. Lett. 4, 35–50 (2015)
Sadeghi, S., Seifi, A., Azizi, E.: Trilevel shortest path network interdiction with partial fortification. Comput. Ind. Eng. 106, 400–411 (2017)
Scheel, H., Scholtes, S.: Mathematical programs with equilibrium constraints: stationarity, optimality, and sensitivity. Math. Oper. Res. 25, 1–22 (2000)
Scholtes, S.: Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim. 11, 918–936 (2001)
Shimizu, K., Ishizuka, Y., Bard, J.F.: Nondifferentiable and Two-Level Mathematical Programming. Kluwer, Dordrecht (1997)
Ward, J.E., Wendell, R.E.: Approaches to sensitivity analysis in linear programming. Ann. Oper. Res. 27(1), 3–38 (1990)
Ye, J.: Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints. J. Math. Anal. Appl. 30, 350–369 (2005)
Zhang, G., Lu, J., Gao, Y.: Multi-level Decision Making: Models, Methods and Applications, vol. 82. Springer, Berlin (2015)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
The first author’s work has been supported by Deutsche Forschungsgemeinschaft, Project DE650/10. The second author’s work has been supported by the Russian Science Foundation, Project 17-11-01021. The last author’s work has been supported by the Ministry of Science and Education of the Russian Federation under the 5-100 Excellence Programme.
Rights and permissions
About this article
Cite this article
Dempe, S., Khamisov, O. & Kochetov, Y. A special three-level optimization problem. J Glob Optim 76, 519–531 (2020). https://doi.org/10.1007/s10898-019-00822-w
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-019-00822-w
Keywords
- Bilevel optimization
- Three-level optimization
- Necessary optimality conditions
- Solution algorithms
- Hierarchical optimization