zbMATH — the first resource for mathematics

Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
An overview of bilevel optimization. (English) Zbl 1159.90483
Summary: This paper is devoted to bilevel optimization, a branch of mathematical programming of both practical and theoretical interest. Starting with a simple example, we proceed towards a general formulation. We then present fields of application, focus on solution approaches, and make the connection with MPECs (Mathematical Programs with Equilibrium Constraints).
MSC:
 90C30 Nonlinear programming 90C33 Complementarity and equilibrium problems; variational inequalities (finite dimensions)
MacMPEC
References:
 [1] Aiyoshi, E., & Shimizu, K. (1981). Hierarchical decentralized systems and its new solution by a barrier method. IEEE Transactions on Systems, Man, and Cybernetics, 11, 444–449. · doi:10.1109/TSMC.1981.4308712 [2] Aiyoshi, E., & Shimizu, K. (1984). A solution method for the static constrained Stackelberg problem via penalty method. IEEE Transactions on Automatic Control, 29, 1111–1114. · Zbl 0553.90104 · doi:10.1109/TAC.1984.1103455 [3] Al-Khayal, F. A., Horst, R., & Pardalos, P. M. (1992). Global optimization of concave functions subject to quadratic constraints: an application in nonlinear bilevel programming. Annals of Operations Research, 34, 125–147. · Zbl 0751.90066 · doi:10.1007/BF02098176 [4] Anandalingam, G., & Friesz, T. (1992). Hierarchical optimization: an introduction. Annals of Operations Research, 34, 1–11. · Zbl 0751.90067 · doi:10.1007/BF02098169 [5] Audet, C., Hansen, P., Jaumard, B., & Savard, G. (1997). Links between linear bilevel and mixed 0-1 programming problems. Journal of Optimization Theory and Applications, 93, 273–300. · Zbl 0901.90153 · doi:10.1023/A:1022645805569 [6] Auslender, A. (1976). Optimisation: méthodes numériques. Paris: Masson. [7] Bard, J. F. (1988). Convex two-level optimization. Mathematical Programming, 40, 15–27. · Zbl 0655.90060 · doi:10.1007/BF01580720 [8] Bard, J. F. (1998). Practical bilevel optimization. Nonconvex optimization and its applications (Vol. 30) Dordrecht: Kluwer Academic. [9] Bard, J. F., & Falk, J. (1982). An explicit solution to the multi-level programming problem. Computers and Operations Research, 9, 77–100. · doi:10.1016/0305-0548(82)90007-7 [10] Bard, J. F., & Moore, J. T. (1990). A branch and bound algorithm for the bilevel programming problem. SIAM Journal of Scientific and Statistical Computing, 11, 281–292. · Zbl 0702.65060 · doi:10.1137/0911017 [11] Bard, J. F., Plummer, J., & Sourie, J. C. (2000). A bilevel programming approach to determining tax credits for biofuel production. European Journal of Operational Research, 120, 30–46. · Zbl 0976.90099 · doi:10.1016/S0377-2217(98)00373-7 [12] Ben-Ayed, O. (1993). Bilevel linear programming. Computers and Operations Research, 20, 485–501. · Zbl 0783.90068 · doi:10.1016/0305-0548(93)90013-9 [13] Ben-Ayed, O., & Blair, C. (1990). Computational difficulties of bilevel linear programming. Operations Research, 38, 556–560. · Zbl 0708.90052 · doi:10.1287/opre.38.3.556 [14] Bi, Z., Calamai, P. H., & Conn, A. R. (1989). An exact penalty function approach for the linear bilevel programming problem. Technical Report #167-O-310789, Department of Systems Design Engineering, University of Waterloo. [15] Bi, Z., Calamai, P. H., & Conn, A. R. (1991). An exact penalty function approach for the nonlinear bilevel programming problem. Technical Report #180-O-170591, Department of Systems Design Engineering, University of Waterloo. [16] Bialas, W., & Karwan, M. (1984). Two-level linear programming. Management Science, 30, 1004–1020. · Zbl 0559.90053 · doi:10.1287/mnsc.30.8.1004 [17] Bialas, W., Karwan, M., & Shaw, J. (1980). A parametric complementarity pivot approach for two-level linear programming. Technical Report 80-2, State University of New York at Buffalo, Operations Research Program. [18] Bracken, J., & McGill, J. (1973). Mathematical programs with optimization problems in the constraints. Operations Research, 21, 37–44. · Zbl 0263.90029 · doi:10.1287/opre.21.1.37 [19] Bracken, J., & McGill, J. (1974). Defense applications of mathematical programs with optimization problems in the constraints. Operations Research, 22, 1086–1096. · Zbl 0292.90057 · doi:10.1287/opre.22.5.1086 [20] Bracken, J., & McGill, J. (1978). Production and marketing decisions with multiple objectives in a competitive environment. Journal of Optimization Theory and Applications, 24, 449–458. · Zbl 0351.90001 · doi:10.1007/BF00932888 [21] Brotcorne, L., Labbé, M., Marcotte, P., & Savard, G. (2001). A bilevel model for toll optimization on a multicommodity transportation network. Transportation Science, 35, 1–14. · Zbl 1069.90502 · doi:10.1287/trsc.35.4.345.10433 [22] Candler, W., & Norton, R. (1977). Multilevel programming. Technical Report 20, World Bank Development Research Center, Washington D.C., USA. [23] Candler, W., & Townsley, R. (1982). A linear two-level programming problem. Computers and Operations Research, 9, 59–76. · doi:10.1016/0305-0548(82)90006-5 [24] Case, L. M. (1999). An 1 penalty function approach to the nonlinear bilevel programming problem. PhD thesis, University of Waterloo, Ontario, Canada. [25] Chen, Y., & Florian, M. (1992). On the geometric structure of linear bilevel programs: a dual approach. Technical Report CRT-867, Centre de Recherche sur les Transports, Université de Montréal, Montréal, QC, Canada. [26] Chen, Y., Florian, M., & Wu, S. (1992). A descent dual approach for linear bilevel programs. Technical Report CRT-866, Centre de Recherche sur les Transports, Université de Montréal, Montréal, QC, Canada. [27] Clarke, F. H. (1990). Optimization and nonsmooth analysis. Philadelphia: SIAM. [28] Colson, B. (September 1999). Mathematical programs with equilibrium constraints and nonlinear bilevel programming problems. Master’s thesis, Department of Mathematics, FUNDP, Namur, Belgium. [29] Colson, B. (October 2002). BIPA (BIlevel programming with approximation methods): software guide and test problems. Technical Report CRT-2002-38, Centre de Recherche sur les Transports, Université de Montréal, Montréal, QC, Canada. [30] Colson, B., Marcotte, P., & Savard, G. (March 2005a). A trust-region method for nonlinear programming: algorithm and computational experience. Computational Optimization and Applications, 30. [31] Colson, B., Marcotte, P., & Savard, G. (2005b). Bilevel programming: a survey. 4OR, 3, 87–107. · Zbl 1134.90482 · doi:10.1007/s10288-005-0071-0 [32] Conn, A. R., Gould, N. I. M., & Toint, Ph. L. (2000). Trust-region methods. Philadelphia: SIAM. [33] Constantin, I., & Florian, M. (1995). Optimizing frequencies in a transit network: a nonlinear bi-level programming approach. International Transactions in Operational Research, 2, 149–164. · Zbl 0868.90037 · doi:10.1111/j.1475-3995.1995.tb00011.x [34] Côté, J.-P., Marcotte, P., & Savard, G. (2003). A bilevel modeling approach to pricing and fare optimization in the airline industry. Journal of Revenue and Pricing Management, 2, 23–36. · doi:10.1057/palgrave.rpm.5170046 [35] Dempe, S. (1992a). A necessary and a sufficient optimality condition for bilevel programming problems. Optimization, 25, 341–354. · Zbl 0817.90104 · doi:10.1080/02331939208843831 [36] Dempe, S. (1992b). Optimality conditions for bilevel programming problems. In P. Kall (Ed.), System modelling and optimization (pp. 17–24). Heidelberg: Springer. [37] Dempe, S. (2002). Foundations of bilevel programming. Nonconvex optimization and its applications, (Vol. 61). Dordrecht: Kluwer Academic. [38] Dempe, S. (2003). Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints. Optimization, 52, 333–359. · Zbl 1140.90493 · doi:10.1080/0233193031000149894 [39] Dirkse, S. P., & Ferris, M. C. (1999). Modeling and solution environments for MPEC: gams & matlab. In M. Fukushima, & L. Qi (Eds.), Reformulation: nonsmooth, piecewise smooth, semismooth and smoothing methods (pp. 127–148). Dordrecht: Kluwer Academic. [40] Edmunds, T., & Bard, J. F. (1991). Algorithms for nonlinear bilevel mathematical programs. IEEE Transactions on Systems, Man, and Cybernetics, 21, 83–89. · doi:10.1109/21.101139 [41] Facchinei, F., Jiang, H., & Qi, L. (1996). A smoothing method for mathematical programs with equilibrium constraints. Technical Report R03-96, Università di Roma ”La Sapienza”, Dipartimento di Informatica e Sistemistica. [42] Falk, J. E., & Liu, J. (1995). On bilevel programming, Part I : general nonlinear cases. Mathematical Programming, 70, 47–72. [43] Fletcher, R., & Leyffer, S. (2002). Numerical experience with solving MPECs by nonlinear programming methods. Numerical Analysis Report NA/210, Department of Mathematics, University of Dundee, Dundee, Scotland. [44] Fletcher, R., Leyffer, S., Ralph, D., & Scholtes, S. (2002). Local convergence of SQP methods for Mathematical Programs with Equilibrium Constraints. Numerical Analysis Report NA/209, Department of Mathematics, University of Dundee, Dundee, Scotland. [45] Florian, M., & Chen, Y. (1995). A coordinate descent method for the bi-level o-d matrix adjustment problem. International Transactions in Operational Research, 2, 165–179. [46] Fortuny-Amat, J., & McCarl, B. (1981). A representation and economic interpretation of a two-level programming problem. Journal of the Operational Research Society, 32, 783–792. [47] Fukushima, M. (1992). Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems. Mathematical Programming, 53, 99–110. · Zbl 0756.90081 · doi:10.1007/BF01585696 [48] Fukushima, M., & Pang, J.-S. (1999). Complementarity constraint qualifications and simplified B-stationarity conditions for mathematical programs with equilibrium constraints. Computational Optimization and Applications, 13, 111–136. · Zbl 1040.90560 · doi:10.1023/A:1008656806889 [49] Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: a guide to the theory of NP-completeness. New York: Freeman. [50] Hansen, P., Jaumard, B., & Savard, G. (September 1992). New branch-and-bound rules for linear bilevel programming. SIAM Journal on Scientific and Statistical Computing, 13, 1194–1217. · Zbl 0760.65063 · doi:10.1137/0913069 [51] Haurie, A., Loulou, R., & Savard, G. (1992). A two player game model of power cogeneration in new england. IEEE Transactions on Automatic Control, 37, 1451–1456. · Zbl 0800.90657 · doi:10.1109/9.159591 [52] Hearn, D. W., & Ramana, M. V. (1998). Solving congestion toll pricing models. In P. Marcotte (Ed.), Equilibrium and advanced transportation modelling (pp. 109–124). Dordrecht: Kluwer Academic. [53] Hobbs, B. F., & Nelson, S. K. (1992). A nonlinear bilevel model for analysis of electric utility demand-side planning issues. Annals of Operations Research, 34, 255–274. · Zbl 0729.91036 · doi:10.1007/BF02098182 [54] Hsu, S., & Wen, U. (1989). A review of linear bilevel programming problems. In Proceedings of the National Science Council, Republic of China, Part A: Physical Science and Engineering (Vol. 13, pp. 53–61). [55] Ishizuka, Y., & Aiyoshi, E. (1992). Double penalty method for bilevel optimization problems. Annals of Operations Research, 34, 73–88. · Zbl 0756.90083 · doi:10.1007/BF02098173 [56] Jaumard, B., Savard, G., & Xiong, J. (January 2000). A new algorithm for the convex bilevel programming problem. Technical Report, Ecole Polytechnique de Montréal. [57] Jeroslow, R. G. (1985). The polynomial hierarchy and a simple model for competitive analysis. Mathematical Programming, 32, 146–164. · Zbl 0588.90053 · doi:10.1007/BF01586088 [58] Jian, H., & Ralph, D. (December 1997). Smooth SQP methods for mathematical programs with nonlinear complementarity constraints. Manuscript, Department of Mathematics and Statistics, University of Melbourne. [59] Júdice, J. J., & Faustino, A. (1988). The solution of the linear bilevel programming problem by using the linear complementarity problem. Investigação Operacional, 8, 77–95. [60] Júdice, J. J., & Faustino, A. (1992). A sequential LCP method for bilevel linear programming. Annals of Operations Research, 34, 89–106. · Zbl 0749.90049 · doi:10.1007/BF02098174 [61] Júdice, J. J., & Faustino, A. (1994). The linear-quadratic bilevel programming problem. Information Systems and Operational Research, 32, 87–98. [62] Kara, B. Y., & Verter, V. (2004). Designing a road network for hazardous materials transportation. Transportation Science, 38, 188–196. · doi:10.1287/trsc.1030.0065 [63] Kolstad, C. D. (1985). A review of the literature on bi-level mathematical programming. Technical Report LA-10284-MS, Los Alamos National Laboratory, Los Alamos, New Mexico, USA. [64] Kolstad, C. D., & Lasdon, L. S. (1990). Derivative estimation and computational experience with large bilevel mathematical programs. Journal of Optimization Theory and Applications, 65, 485–499. · Zbl 0676.90101 · doi:10.1007/BF00939562 [65] Labbé, M., Marcotte, P., & Savard, G. (1998). A bilevel model of taxation and its applications to optimal highway pricing. Management Science, 44, 1595–1607. · Zbl 1004.90510 · doi:10.1287/mnsc.44.12.1595 [66] Larsson, T., & Patriksson, M. (1998). Side constrained traffic equilibrium models–traffic management through link tolls. In P. Marcotte, S. Nguyen (Eds.), Equilibrium and advanced transportation modelling (pp. 125–151). Dordrecht: Kluwer Academic. [67] LeBlanc, L. J. (1973). Meathematical programming algorithms for large scale network equilibrium and network design problems. PhD thesis, Northwestern University, Evanston, Illinois. [68] Leyffer, S. MacMPEC–AMPL collection of Mathematical Programs with Equilibrium Constraints. Available at http://www-unix.mcs.anl.gov/$\sim$leyffer/MacMPEC/ . [69] Liu, G., Han, J., & Wang, S. (May 1998). A trust region algorithm for bilevel programming problems. Chinese Science Bulletin, 43, 820–824. · Zbl 0984.90041 · doi:10.1007/BF03182744 [70] Loridan, P., & Morgan, J. (1996). Weak via strong Stackelberg problem: new results. Journal of Global Optimization, 8, 263–287. · Zbl 0861.90151 · doi:10.1007/BF00121269 [71] Luo, Z.-Q., Pang, J.-S., & Ralph, D. (1996). Mathematical programs with equilibrium constraints. Cambridge: Cambridge University Press. [72] Marcotte, P. (1986). Network design problem with congestion effects: a case of bilevel programming. Mathematical Programming, 34, 23–36. · Zbl 0604.90053 · doi:10.1007/BF01580580 [73] Marcotte, P., & Savard, G. (2005). Bilevel programming: a combinatorial perspective. In: D. Avis, A. Hertz, & O. Marcotte (Eds.), Graph theory and combinatorial optimization. Boston: Kluwer Academic. [74] Marcotte, P., & Zhu, D. L. (1996). Exact and inexact penalty methods for the generalized bilevel programming problem. Mathematical Programming, 74, 141–157. [75] Marcotte, P., Savard, G., & Semet, F. (2004). A bilevel programming approach to the travelling salesman problem. Operations Research Letters, 32, 240–248. · Zbl 1045.90052 · doi:10.1016/j.orl.2003.08.005 [76] Migdalas, A. (1995). Bilevel programming in traffic planning: models, methods and challenge. Journal of Global Optimization, 7, 381–405. · Zbl 0844.90050 · doi:10.1007/BF01099649 [77] Migdalas, A., Pardalos, P. M., & Värbrand, P. (Eds.) (1997). Multilevel optimization: algorithms and applications, nonconvex optimization and its applications (Vol. 20). Dordrecht: Kluwer Academic. [78] Nash, J. (1951). Non-cooperative games. Annals of Mathematics, 54, 286–295. · Zbl 0045.08202 · doi:10.2307/1969529 [79] Outrata, J. (1993). Necessary optimality conditions for Stackelberg problems. Journal of Optimization Theory and Applications, 76, 305–320. · Zbl 0802.49007 · doi:10.1007/BF00939610 [80] Outrata, J. (1994). On optimization problems with variational inequality constraints. SIAM Journal on Optimization, 4, 340–357. · Zbl 0826.90114 · doi:10.1137/0804019 [81] Outrata, J., & Kocvara, M. (2006). Effective reformulations of the truss topology design problem. Optimization and Engineering, 7, 201–219. · Zbl 1175.74068 · doi:10.1007/s11081-006-6839-z [82] Outrata, J., Kočvara, M., & Zowe, J. (1998). Nonsmooth approach to optimization problems with equilibrium constraints: theory, applications and numerical results, Nonconvex optimization and its applications (Vol. 28). Dordrecht: Kluwer Academic. [83] Pang, J. S., & Trinkle, J. C. (1996). Complementarity formulations and existence of solutions of dynamic multi-rigid-body contact problems with coulomb friction. Mathematical Programming, 73, 199–226. · Zbl 0854.70008 · doi:10.1007/BF02592103 [84] Papavassilopoulos, G. (1982). Algorithms for static Stackelberg games with linear costs and polyhedral constraints. In Proceedings of the 21st IEEE Conference on Decisions and Control (pp. 647–652). [85] Patriksson, M. (1994). The traffic assignment problem–models and methods. Utrecht: VSP BV. [86] Ralph, D. (November 1998). Optimization with equilibrium constraints: a piecewise SQP approach. Manuscript, Department of Mathematics and Statistics, University of Melbourne. [87] Savard, G. (April 1989). Contribution à la programmation mathématique à deux niveaux. PhD thesis, Ecole Polytechnique de Montréal, Université de Montréal, Montréal, QC, Canada. [88] Savard, G., & Gauvin, J. (1994). The steepest descent direction for the nonlinear bilevel programming problem. Operations Research Letters, 15, 265–272. · Zbl 0816.90122 · doi:10.1016/0167-6377(94)90086-8 [89] Scheel, H., & Scholtes, S. (2000). Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity. Mathematics of Operations Research, 25, 1–22. · Zbl 1073.90557 · doi:10.1287/moor.25.1.1.15213 [90] Scholtes, S. (2001). Convergence properties of a regularisation scheme for mathematical programs with complementarity constraints. SIAM Journal on Optimization, 11, 918–936. · Zbl 1010.90086 · doi:10.1137/S1052623499361233 [91] Scholtes, S. (May 2002). Combinatorial structures in nonlinear programming. Optimization Online. Available on the Internet at the address http://www.optimization-online.org/DB_HTML/2002/05/477.html . [92] Scholtes, S., & Stöhr, M. (1999). Exact penalization of mathematical programs with equilibrium constraints. SIAM Journal on Control and Optimization, 37, 617–652. · Zbl 0922.90128 · doi:10.1137/S0363012996306121 [93] Sherali, H. D., Soyster, A. L., & Murphy, F. H. (1983). Stackelberg-Nash-Cournot equilibria: characterizations and computations. Operations Research, 31, 253–276. · Zbl 0506.90011 · doi:10.1287/opre.31.2.253 [94] Shimizu, K., & Aiyoshi, E. (1981). A new computational method for Stackelberg and min-max problems by use of a penalty method. IEEE Transactions on Automatic Control, 26, 460–466. · Zbl 0472.93004 · doi:10.1109/TAC.1981.1102607 [95] Shimizu, K., Ishizuka, Y., & Bard, J. F. (1997). Nondifferentiable and two-level mathematical programming. Dordrecht: Kluwer Academic. [96] Stackelberg, H. (1952). The theory of market economy. Oxford: Oxford University Press. [97] Thoai, N. V., Yamamoto, Y., & Yoshise, A. (May 2002). Global optimization method for solving mathematical programs with linear complementarity constraints. Discussion Paper No. 987, Institute of Policy and Planning Sciences, University of Tsukuba, Japan. [98] Tuy, H., Migdalas, A., & Värbrand, P. (1993). A global optimization approach for the linear two-level program. Journal of Global Optimization, 3, 1–23. · Zbl 0771.90108 · doi:10.1007/BF01100237 [99] Van Ackere, A. (1993). The principal/agent paradigm: characterizations and computations. European Journal of Operations Research, 70, 83–103. · Zbl 0800.90271 · doi:10.1016/0377-2217(93)90234-E [100] Vicente, L. N., & Calamai, P. H. (1994). Bilevel and multilevel programming: a bibliography review. Journal of Global Optimization, 5, 291–306. · Zbl 0822.90127 · doi:10.1007/BF01096458 [101] Vicente, L. N., & Calamai, P. H. (1995). Geometry and local optimality conditions for bilevel programs with quadratic strictly convex lower levels. In: D. Du, & M. Pardalos (Eds.), Minimax and applications. Nonconvex optimization and its applications (Vol. 4, pp. 141–151). Dordrecht: Kluwer Academic. [102] Vicente, L. N., Savard, G., & Júdice, J. J. (1994). Descent approaches for quadratic bilevel programming. Journal of Optimization Theory and Applications, 81, 379–399. · Zbl 0819.90076 · doi:10.1007/BF02191670 [103] Vicente, L. N., Savard, G., & Júdice, J. J. (1996). The discrete linear bilevel programming problem. Journal of Optimization Theory and Applications, 89, 597–614. · Zbl 0851.90084 · doi:10.1007/BF02275351 [104] Wen, U., & Hsu, S. (1991). Linear bi-level programming problems–a review. Journal of the Operational Research Society, 42, 125–133. [105] Ye, J. J., & Zhu, D. L. (1995). Optimality conditions for bilevel programming problems. Optimization, 33, 9–27. · Zbl 0820.65032 · doi:10.1080/02331939508844060 [106] Yezza, A. (1996). First-order necessary optimality conditions for general bilevel programming problems. JOTA, 89, 189–219. · Zbl 0866.90119 · doi:10.1007/BF02192648