Skip to main content
SpringerLink
Log in

Numerical solution of a class of bilevel programming problems

  • Published:
Numerical Analysis and Applications Aims and scope Submit manuscript

Abstract

A quadratic-linear bilevel programming problem is considered. Its optimistic statement is reduced to a series of nonconvex unilevel problems. An approximate algorithm for global search in reduced problems is proposed. Numerical solutions of randomly generated test problems are given and analyzed.

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. Germeier, Yu.B., Igry s neprotivopolzhnymi interesami (Games with Nonopposite Interests), Moscow: Nauka, 1976.

    Google Scholar 

  2. Gorelik, V.A. and Kononenko, A.F., Teoretiko-igrovye modeli prinyatiya reshenii v ekologo-ekonomicheskikh sistemakh (Game-Theoretic Models for Decision-Making in Ekologo-Economic Systems), Moscow: Radio i svyaz, 1982.

    Google Scholar 

  3. Vasin, A.A. and Morozov, V.V., Teoriya igr i modeli matematicheskoi ekonomiki (Game Theory and Mathematical EconomicModels), Moscow: MAKS, 2005.

    Google Scholar 

  4. Bard, J.F., Practical Bilevel Optimization, Dordrecht: Kluwer, 1998.

    MATH  Google Scholar 

  5. Dempe, S., Foundations of Bilevel Programming, Dordrecht: Kluwer, 2002.

    MATH  Google Scholar 

  6. Colson, B., Marcotte, P., and Savard, G., An Overview of Bilevel Optimization, Ann. Operat. Res., 2007, vol. 153, no. 1, pp. 235–256.

    Article  MATH  MathSciNet  Google Scholar 

  7. Saboia, C.H., Campelo, M., and Scheimberg, S., A Computational Study of Global Algorithms for Linear Bilevel Programming, Num. Algor., 2004, vol. 35, nos. 2–4, pp. 155–173.

    Article  MATH  Google Scholar 

  8. Audet, C., Savard, G., and Zghal, W., New Branch-and-Cut Algorithm for Bilevel Linear Programming, J. Optim. Th. Appl., 2007, vol. 134, no. 2, pp. 53–370.

    Article  MathSciNet  Google Scholar 

  9. Muu, L.D. and Quy, N.V., A Global Optimization Method for Solving Convex Quadratic Bilevel Programming Problems, J. Glob. Optim., 2003, vol. 26, no. 2, pp. 199–219.

    Article  MATH  MathSciNet  Google Scholar 

  10. Li, H. and Wang, Y., A Hybrid Genetic Algorithm for Solving a Class of Nonlinear Bilevel Programming Problems, Proc. 6th Int. Conf. Simulated Evolution and Learning, Wang, T.D., Li, X., et al., Eds., Hetei, China, 2006, pp. 408–415.

  11. Bard, J.F., Convex Two-Level Optimization, Math. Programm., 1988, vol. 40, no. 1, pp. 15–27.

    Article  MATH  MathSciNet  Google Scholar 

  12. Gumus, Z.H. and Floudas, C.A., Global Optimization of Nonlinear Bilevel Programming Problems, J. Glob. Optim., 2001, vol. 20, no. 1, pp. 1–31.

    Article  MathSciNet  Google Scholar 

  13. Colson, B., Marcotte, P., and Savard, G., A Trust-Region Method for Nonlinear Bilevel Programming: Algorithm and Computational Experience, Comput. Optim. Appl., 2005, vol. 30, no. 3, pp. 211–227.

    Article  MATH  MathSciNet  Google Scholar 

  14. Strekalovsky, A.S, Orlov, A.V., and Malyshev, A.V., Local Search in a Quadratic-Linear Bilevel Programming Problem, Sib. Zh. Vych. Mat., 2010, vol. 13, no. 1, pp. 75–88.

    Google Scholar 

  15. Vasiliev, F.P., Metody optimizatsii (Optimization Methods), Moscow: Faktorial, 2002.

    Google Scholar 

  16. Bazara, M. and Shetti, K., Nelineinoe programmirovanie. Teoriya i algoritmy (Nonlinear Programming: Theory and Algorithms),Moscow: Mir, 1982.

    Google Scholar 

  17. Strekalovsky, A.S., Elementy nevypukloi optmizatsii (Elements of Nonconvex Optimization), Novosibirsk: Nauka, 2003.

    Google Scholar 

  18. Strekalovsky, A.S., Minimization of a Difference between Two Convex Functions on an Admissible Set, Zh. Vych. Mat.Mat. Fiz., 2003, vol. 43, no. 3, pp. 399–409.

    Google Scholar 

  19. Strekalovsky, A.S. and Orlov, A.V., Bimatrichnye igry i bilineinoe programmirovanie (Bimatrix Games and Bilinear Programming), Moscow: Fizmatlit, 2007.

    Google Scholar 

  20. Strekalovsky, A.S. and Orlov, A.V., A New Approach to Nonconvex Optimization, Vych. Met. Progr., 2007, vol. 8, no. 2, pp. 11–27.

    Google Scholar 

  21. Orlov, A.V. and Strekalovsky, A.S., Numerical Search for Equilibrium Situations in Bimatrix Games, Zh. Vych. Mat.Mat. Fiz., 2005, vol. 45, no. 6, pp. 983–997.

    MATH  Google Scholar 

  22. Vasiliev, I.L., Klimentova, K.B., and Orlov, A.V., Parallel Global Search for EquilibriumSituations in Bimatrix Games, Vych. Met. Progr., 2007, vol. 8, no. 2, pp. 84–94.

    Google Scholar 

  23. Orlov, A.V., Numerical Solution of Bilinear Programming Problems, Zh. Vych. Mat. Mat. Fiz., 2008, vol. 48, no. 2, pp. 45–62.

    Google Scholar 

  24. Calamai, P. and Vicente, L., Generating Linear and Linear-Quadratic Bilevel Programming Problems, SIAM J. Sci. Comput., 1993, vol. 14, no. 4, pp. 770–782.

    Article  MATH  MathSciNet  Google Scholar 

  25. Calamai, P. and Vicente, L., Generating Quadratic Bilevel Programming Test Problems, ACM Trans.Math. Soft., 1994, vol. 20, pp. 103–119.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of System Dynamics and Control Theory, Siberian Branch, Russian Academy of Sciences, ul. Lermontova 134, Irkutsk, 664033, Russia

    A. S. Strekalovsky, A. V. Orlov & A. V. Malyshev

Authors
  1. A. S. Strekalovsky
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. A. V. Orlov
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. A. V. Malyshev
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to A. S. Strekalovsky.

Additional information

Original Russian Text © A.S. Strekalovsky, A.V. Orlov, and A.V. Malyshev, 2010, published in Sibirskii Zhurnal Vychislitel’noi Matematiki, 2010, Vol. 13, No. 2, pp. 201–212.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Strekalovsky, A.S., Orlov, A.V. & Malyshev, A.V. Numerical solution of a class of bilevel programming problems. Numer. Analys. Appl. 3, 165–173 (2010). https://doi.org/10.1134/S1995423910020059

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1134/S1995423910020059

Key words

Search

Navigation