A Fully Bayesian Approach to Bilevel Problems | SpringerLink
Skip to main content
Springer Nature Link
Log in

A Fully Bayesian Approach to Bilevel Problems

  • Conference paper
  • First Online:
Algorithmic Decision Theory (ADT 2024)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 15248))

Included in the following conference series:

  • 90 Accesses

Abstract

The mathematical models of many real-world decision-making problems contain two levels of optimization. In these models, one of the optimization problems appears as a constraint of the other one, called follower and leader, respectively. These problems are known as bilevel optimization problems (BOPs) in mathematical programming and are widely studied by both classical and evolutionary optimization communities. The nested nature of these problems causes many difficulties such as non-convexity and disconnectedness for traditional methods, and requires a huge number of function evaluations for evolutionary algorithms. This paper proposes a fully Bayesian optimization approach, called FB-BLO. We aim to reduce the necessary function evaluations for both upper and lower level problems by iteratively approximating promising solutions with Gaussian process surrogate models at both levels. The proposed FB-BLO algorithm uses the other decision-makers’ observations in its Gaussian process model to leverage the correlation between decisions and objective values. This allows us to extract knowledge from previous decisions for each level. The algorithm has been evaluated on numerous benchmark problems and compared with existing state-of-the-art algorithms. Our evaluation demonstrates the success of our proposed FB-BLO algorithm in terms of both effectiveness and efficiency.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 6634
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 8293
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Angelo, J.S., Krempser, E., Barbosa, H.J.: Differential evolution for bilevel programming. In: IEEE Congress on Evolutionary Computation, pp. 470–477 (2013)

    Google Scholar 

  2. Authors, T.G.: GPyOpt: a Bayesian optimization framework in python (2016)

    Google Scholar 

  3. Bard, J.F., Falk, J.E.: An explicit solution to the multi-level programming problem. Comput. Oper. Res. 9(1), 77–100 (1982)

    Article  MathSciNet  Google Scholar 

  4. Bracken, J., McGill, J.T.: Mathematical programs with optimization problems in the constraints. Oper. Res. 21(1), 37–44 (1973)

    Article  MathSciNet  Google Scholar 

  5. Bracken, J., McGill, J.T.: Defense applications of mathematical programs with optimization problems in the constraints. Oper. Res. 22(5), 1086–1096 (1974)

    Article  MathSciNet  Google Scholar 

  6. Cai, X., Gao, L., Li, X.: Efficient generalized surrogate-assisted evolutionary algorithm for high-dimensional expensive problems. IEEE Trans. Evol. Comput. 24(2), 365–379 (2020)

    Article  Google Scholar 

  7. Camacho, J.F., Corpus, C., Villegas, J.G.: Metaheuristics for bilevel optimization: a comprehensive review. Comput. Oper. Res. 161, 106410 (2024)

    Article  MathSciNet  Google Scholar 

  8. Chen, L., Liu, H.L., Li, K., Tan, K.C.: Evolutionary bi-level optimization via multi-objective transformation-based lower level search. IEEE Trans. Evol. Comput. 1 (2023)

    Google Scholar 

  9. Colson, B., Marcotte, P., Savard, G.: A trust-region method for nonlinear bilevel programming: algorithm and computational experience. Comput. Optim. Appl. 30, 211–227 (2005)

    Article  MathSciNet  Google Scholar 

  10. Cox, D.D., John, S.: SDO: a statistical method for global optimization. In: Multidisciplinary Design Optimization: State-of-the-Art, pp. 315–329 (1997)

    Google Scholar 

  11. Dogan, V., Prestwich, S.: Bayesian optimization with multi-objective acquisition function for bilevel problems. In: Longo, L., O’Reilly, R. (eds.) AICS 2022. CCIS, vol. 1662, pp. 409–422. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-26438-2_32

    Chapter  Google Scholar 

  12. Dogan, V., Prestwich, S.: Bilevel optimization by conditional Bayesian optimization. In: Nicosia, G., Ojha, V., La Malfa, E., La Malfa, G., Pardalos, P.M., Umeton, R. (eds.) LOD 2023, Part I. LNCS, vol. 14505, pp. 243–258. Springer, Heidelberg (2024). https://doi.org/10.1007/978-3-031-53969-5_19

    Chapter  Google Scholar 

  13. Edmunds, T., Bard, J.: Algorithms for nonlinear bilevel mathematical programs. IEEE Trans. Syst. Man Cybern. 21(1), 83–89 (1991)

    Article  MathSciNet  Google Scholar 

  14. Frazier, P.: A tutorial on Bayesian optimization. ArXiv abs/1807.02811 (2018)

    Google Scholar 

  15. Girigoudar, K., Roald, L.A.: Identifying secure operating ranges for der control using bilevel optimization. IEEE Trans. Smart Grid 15(3), 2921–2933 (2024)

    Article  Google Scholar 

  16. Hansen, P., Jaumard, B., Savard, G.: New branch-and-bound rules for linear bilevel programming. SIAM J. Sci. Stat. Comput. 13(5), 1194–1217 (1992)

    Article  MathSciNet  Google Scholar 

  17. Haywood, A.B., Lunday, B.J., Robbins, M.J.: Intruder detection and interdiction modeling: a bilevel programming approach for ballistic missile defense asset location. Omega 110, 102640 (2022)

    Article  Google Scholar 

  18. He, X., Zhou, Y., Chen, Z.: Evolutionary bilevel optimization based on covariance matrix adaptation. IEEE Tran. Evol. Comput. 23(2), 258–272 (2019)

    Article  Google Scholar 

  19. Hong, Q., Meng, F., Liu, J., Bo, R.: A bilevel game-theoretic decision-making framework for strategic retailers in both local and wholesale electricity markets. Appl. Energy 330, 120311 (2023)

    Article  Google Scholar 

  20. Jiang, H., Chou, K., Tian, Y., Zhang, X., Jin, Y.: Efficient surrogate modeling method for evolutionary algorithm to solve bilevel optimization problems. IEEE Trans. Cybern. 1–13 (2023)

    Google Scholar 

  21. Kieffer, E., Danoy, G., Bouvry, P., Nagih, A.: Bayesian optimization approach of general bi-level problems. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO 2017, pp. 1614–1621. Association for Computing Machinery, New York (2017)

    Google Scholar 

  22. Kleinert, T., Labbé, M., Plein, F., Schmidt, M.: Technical note—there’s no free lunch: on the hardness of choosing a correct big-M in bilevel optimization. Oper. Res. 68 (2020)

    Google Scholar 

  23. Li, X., Tian, P., Min, X.: A hierarchical particle swarm optimization for solving bilevel programming problems. In: Rutkowski, L., Tadeusiewicz, R., Zadeh, L.A., Żurada, J.M. (eds.) ICAISC 2006. LNCS (LNAI), vol. 4029, pp. 1169–1178. Springer, Heidelberg (2006). https://doi.org/10.1007/11785231_122

    Chapter  Google Scholar 

  24. Liu, D.C., Nocedal, J.: On the limited memory BFGS method for large scale optimization. Math. Program. 45(1), 503–528 (1989)

    Article  MathSciNet  Google Scholar 

  25. Rasmussen, C.E.: Gaussian processes in machine learning. In: Bousquet, O., von Luxburg, U., Rätsch, G. (eds.) ML -2003. LNCS (LNAI), vol. 3176, pp. 63–71. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-28650-9_4

    Chapter  Google Scholar 

  26. Sinha, A., Lu, Z., Deb, K., Malo, P.: Bilevel optimization based on iterative approximation of mappings. J. Heuristics 26 (2020)

    Google Scholar 

  27. Sinha, A., Malo, P., Deb, K.: Test problem construction for single-objective bilevel optimization. Evol. Comput. 22 (2013)

    Google Scholar 

  28. Sinha, A., Malo, P., Deb, K.: Efficient evolutionary algorithm for single-objective bilevel optimization (2013)

    Google Scholar 

  29. Sinha, A., Malo, P., Deb, K.: Evolutionary algorithm for bilevel optimization using approximations of the lower level optimal solution mapping. Eur. J. Oper. Res. 257(2), 395–411 (2017)

    Article  MathSciNet  Google Scholar 

  30. Sinha, A., Malo, P., Deb, K.: Evolutionary algorithm for bilevel optimization using approximations of the lower level optimal solution mapping. Eur. J. Oper. Res. 257, 395–411 (2017)

    Article  MathSciNet  Google Scholar 

  31. Sinha, A., Malo, P., Deb, K.: A review on bilevel optimization: from classical to evolutionary approaches and applications. IEEE Trans. Evol. Comput. 22(2), 276–295 (2018)

    Article  Google Scholar 

  32. Sinha, A., Soun, T., Deb, K.: Evolutionary bilevel optimization using KKT proximity measure. In: IEEE Congress on Evolutionary Computation, pp. 2412–2419 (2017)

    Google Scholar 

  33. von Stackelberg, H.: Marktform und Gleichgewicht. Die Handelsblatt-Bibliothek “Klassiker der Nationalökonomie” (1934)

    Google Scholar 

  34. Stein, M.: Large sample properties of simulations using Latin hypercube sampling. Technometrics 29(2), 143–151 (1987)

    Article  MathSciNet  Google Scholar 

  35. Vicente, L., Savard, G., Júdice, J.: Descent approaches for quadratic bilevel programming. J. Optim. Theory Appl. 81(2), 379–399 (1994)

    Article  MathSciNet  Google Scholar 

  36. Wang, G., Shan, S.: Review of metamodeling techniques in support of engineering design optimization. J. Mech. Design 129 (2007)

    Google Scholar 

  37. Wang, H., Feng, L., Jin, Y., Doherty, J.: Surrogate-assisted evolutionary multitasking for expensive minimax optimization in multiple scenarios. IEEE Comput. Intell. Mag. 16(1), 34–48 (2021)

    Article  Google Scholar 

  38. Wein, L.: Or forum—homeland security: from mathematical models to policy implementation. Oper. Res. 57, 801–811 (2009)

    Article  Google Scholar 

  39. White, D.J., Anandalingam, G.: A penalty function approach for solving bi-level linear programs. J. Global Optim. 3, 397–419 (1993)

    Article  MathSciNet  Google Scholar 

  40. Yan, S., Wang, W., Li, X., Lv, H., Fan, T., Aikepaer, S.: Stochastic optimal scheduling strategy of cross-regional carbon emissions trading and green certificate trading market based on stackelberg game. Renew. Energy 219, 119268 (2023)

    Article  Google Scholar 

  41. Yin, Y.: Genetic-algorithms-based approach for bilevel programming models. J. Transp. Eng.-ASCE 126 (2000)

    Google Scholar 

  42. Zhang, Q., Liu, S.Q., D’Ariano, A., Chung, S.H., Masoud, M., Li, X.: A bi-level programming methodology for decentralized mining supply chain network design. Expert Syst. Appl. 250, 123904 (2024)

    Article  Google Scholar 

  43. Zheng, A.Y., He, T., Qiu, Y., Wang, M., Wipf, D.: BloomGML: graph machine learning through the lens of bilevel optimization (2024)

    Google Scholar 

Download references

Acknowledgments

This publication has emanated from research conducted with the financial support of Science Foundation Ireland under Grant number 12/RC/2289-P2 at Insight the SFI Research Centre for Data Analytics at UCC, which is co-funded under the European Regional Development Fund. For Open Access, the author has applied a CC BY public copyright licence to any Author Accepted Manuscript version arising from this submission. The authors have no competing interests to declare that are relevant to the content of this article.

Author information

Authors and Affiliations

  1. Insight SFI Research Centre for Data Analytics, School of Computer Science and IT, University College Cork, Cork, Ireland

    Vedat Dogan, Steven Prestwich & Barry O’Sullivan

Authors
  1. Vedat Dogan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Steven Prestwich
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Barry O’Sullivan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Vedat Dogan .

Editor information

Editors and Affiliations

  1. University of Virginia, Charlottesville, USA

    Rupert Freeman

  2. Tulane University, New Orleans, LA, USA

    Nicholas Mattei

Rights and permissions

Reprints and permissions

Copyright information

© 2025 The Author(s), under exclusive license to Springer Nature Switzerland

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Dogan, V., Prestwich, S., O’Sullivan, B. (2025). A Fully Bayesian Approach to Bilevel Problems. In: Freeman, R., Mattei, N. (eds) Algorithmic Decision Theory. ADT 2024. Lecture Notes in Computer Science(), vol 15248. Springer, Cham. https://doi.org/10.1007/978-3-031-73903-3_10

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-73903-3_10

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-73902-6

  • Online ISBN: 978-3-031-73903-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation