Skip to main content
SpringerLink
Log in

The bilevel programming problem: reformulations, constraint qualifications and optimality conditions

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

We consider the bilevel programming problem and its optimal value and KKT one level reformulations. The two reformulations are studied in a unified manner and compared in terms of optimal solutions, constraint qualifications and optimality conditions. We also show that any bilevel programming problem where the lower level problem is linear with respect to the lower level variable, is partially calm without any restrictive assumption. Finally, we consider the bilevel demand adjustment problem in transportation, and show how KKT type optimality conditions can be obtained under the partial calmness, using the differential calculus of Mordukhovich.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Abrahamsson, T.: Estimation of origin-destination matrices using traffic counts: a literature survey. Interim Report IR-98-021/May, Int. Inst. Appl. Syst. Anal., Laxenburg, Austria. http://www.iiasa.ac.at/Admin/PUB/Documents/IR-98-021.pdf (1998)

  2. Beckmann M., Mcguire C.B., Winsten C.B.: Studies in the Economics of Transportation. Yale University Press, New Haven (1956)

    Google Scholar 

  3. Chen, Y.: Bilevel programming problems: analysis, algorithms and applications. PhD Thesis, Centre de Recherche sur les Transports, Université de Montréal, CRT-984 (1994)

  4. Chen Y., Florian M. et al.: Congested O-D trip demand adjustement problem: bilevel programming for mulation and optimality conditions. In: Migdalas, A. (ed) Multilevel Optimization Algorithms and Applications, pp. 1–22. Kluwer Academic Publishers, Dordrecht (1998)

    Chapter  Google Scholar 

  5. Dempe S.: Foundations of Bilevel Programming. Kluwer Academic Publishers, Dordrecht (2002)

    MATH  Google Scholar 

  6. Dempe, S., Dutta, J.: Is bilevel programming a special case of mathematical programming with equilibrium constraints? Math. Program. (2010). doi:10.1007/s10107-010-0342-1

  7. Dempe S., Dutta J., Mordukhovich B.S.: New necessary optimality conditions in optimistic bilevel programming. Optimization 56, 577–604 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  8. Dempe S., Dutta J., Mordukhovich B.S.: Variational analysis in bilevel programming. In: Neogy, S.K., Bapat, R.B., Das, A.K., Parthasarathy, T. (eds) Statistical Science and Interdisciplinary Research 1, Mathematical Programming and Game Theory for Decision Making, pp. 257–277. World Scientific, Hackensack (2008)

    Chapter  Google Scholar 

  9. Dempe, S., Zemkoho, A.B.: Bilevel road pricing: theoretical analysis and optimality conditions. Ann. Oper. Res. (2011). doi:10.1007/s10479-011-1023-z

  10. Dempe S., Zemkoho A.B.: On the Karush-Kuhn-Tucker reformulation of the bilevel optimization problem. Nonlinear Anal. 75, 1202–1218 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  11. Dempe S., Zemkoho A.B.: The generalized Mangasarian-Fromowitz constraint qualification and optimality conditions for bilevel programs. J. Optim. Theory Appl. 148, 433–441 (2011)

    Article  MathSciNet  Google Scholar 

  12. Dempe, S., Zemkoho, A.B.: A bilevel approach for traffic management in capacitated networks. Preprint 2008-05, Fakultät für Mathematik und Informatik, TU Bergakademie Freiberg (2008)

  13. Dinh N., Mordukhovich B.S., Nghia T.T.A.: Subdifferentials of value functions and optimality conditions for DC and bilevel infinite and semi-infinite programs. Math. Program. Ser. B 123, 101–138 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  14. Fisk C.S.: On combining maximum maximum entropy trip matrix with useroptimal assigment. Transp. Res. 22B, 69–73 (1988)

    Article  MathSciNet  Google Scholar 

  15. Flegel, M.: Constraint qualification and stationarity concepts for mathematical programs with equilibrium constraints. PhD Thesis, Institute of Applied Mathematics and Statistics, University of Würzburg (2005)

  16. Henrion R., Surowiec T.M.: On calmness conditions in convex bilevel programming. Appl. Anal. 90, 951–970 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  17. Lu S.: Sensitivity of static traffic user equilibria with perturbations in arc cost function and travel demand. Transp. Sci. 42, 105–123 (2008)

    Article  Google Scholar 

  18. Mangasarian O.L., Shiau T.-H.: Lipschitz continuity of solutions of linear inequalities, programs and complementarity problems. SIAM J. Control Optim. 25, 583–595 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  19. Migdalas A.: Bilevel programming in traffic planning: models, methods and challenge. J. Global Optim. 7, 381–405 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  20. Mirrlees J.A.: The theory of moral hazard and unobservable behaviour. Rev. Econ. Stud. 66, 3–21 (1999)

    Article  MATH  Google Scholar 

  21. Mordukhovich B.S.: Maximum principle in the problem of time optimal response with nonsmooth constraints. J. Appl. Math. Mech. 40, 960–969 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  22. Mordukhovich B.S.: Variational Analysis and Generalized Differentiation. I: Basic Theory. II: Applications. Springer, Berlin (2006)

    Google Scholar 

  23. Mordukhovich B.S., Nam N.M.: Variational stability and marginal functions via generalized differentiation. Math. Oper. Res. 30, 800–816 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  24. Mordukhovich B.S., Nam N.M., Yen N.D.: Subgradients of marginal functions in parametric mathematical programming. Math. Program. 116, 369–396 (2007)

    Article  MathSciNet  Google Scholar 

  25. Mordukhovich B.S., Outrata J.V.: Coderivative analysis of quasi-variational inequalities with applications to stability and optimization. SIAM J. Optim. 18, 389–412 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  26. Outrata J.V.: A note on the usage of nondifferentiable exact penalties in some special optimization problems. Kybernetika 24, 251–258 (1988)

    MathSciNet  MATH  Google Scholar 

  27. Outrata J.V.: On the numerical solution of a class of Stackelberg problems. Z. Oper. Res. 34, 255–277 (1990)

    MathSciNet  MATH  Google Scholar 

  28. Patriksson M.: The Traffic Assignment Problem—Models and Methods. VSP BV, Utrecht, The Netherlands (1994)

    Google Scholar 

  29. Rockafellar R.T.: Convex Analysis. Princeton University Press, New Jersey (1970)

    MATH  Google Scholar 

  30. Rockafellar R.T., Wets R.J.-B.: Variational Analysis. Springer, Berlin (1998)

    Book  MATH  Google Scholar 

  31. Scheel H., Scholtes S.: Mathematical programs with complementarity constraints: stationarity, optimality, and sensitivity. Math. Oper. Res. 25, 1–22 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  32. Surowiec, T.M.: Explicit stationary conditions and solution characterization for equilibrium problems with equilibrium constraints. PhD Thesis, Mathematisch-Naturwissentschaften Fakultät II, Humbolt Universität zu Berlin (2010)

  33. Wardrop J.G.: Some theoretical aspects of road traffic research. Proc. Inst. Civil Engeneers Part II, 325–378 (1952)

    Google Scholar 

  34. Yang H.: Heuristic algorithms for the bilevel origin-destination matrix estimation problem. Transp. Res. 29B, 231–242 (1995)

    Article  Google Scholar 

  35. Yang H., Sasaki T., Iida Y., Asakura Y.: Estimation of origin-destination matrices from traffic counts on congested networks. Transp. Res. 26B, 417–434 (1992)

    Article  Google Scholar 

  36. Ye J.J.: Nondifferentiable multiplier rules for optimization and bilevel optimization problems. SIAM J. Optim. 15, 252–274 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  37. Ye J.J., Zhu D.L.: New necessary optimality conditions for bilevel programs by combining MPEC and the value function approach. SIAM J. Optim. 20, 1885–1905 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  38. Ye J.J.: New uniform parametric error bounds. J. Optim. Theory Appl. 98, 197–219 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  39. Ye J.J., Ye X.Y.: Necessary optimality conditions for optimization problems with variational inequality constraints. Math. Oper. Res. 22, 977–997 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  40. Ye J.J., Zhu D.L.: Optimality conditions for bilevel programming problems. Optimization 33, 9–27 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  41. Ye J.J., Zhu D.L., Zhu Q.J.: Exact penalization and necessary optimality conditions for generalized bilevel programming problems. SIAM J. Optim. 7, 481–507 (1997)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Numerische Mathematik und Optimierung, Technische Universität Bergakademie Freiberg, Akademie Straße 6, 09596, Freiberg, Germany

    S. Dempe & A. B. Zemkoho

Authors
  1. S. Dempe
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. A. B. Zemkoho
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to A. B. Zemkoho.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Dempe, S., Zemkoho, A.B. The bilevel programming problem: reformulations, constraint qualifications and optimality conditions. Math. Program. 138, 447–473 (2013). https://doi.org/10.1007/s10107-011-0508-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-011-0508-5

Keywords

Mathematics Subject Classification (2000)

Search

Navigation