IDEAS home Printed from https://ideas.repec.org/a/eee/oprepe/v13y2024ics2214716024000198.html
   My bibliography  Save this article

δ-perturbation of bilevel optimization problems: An error bound analysis

Author

Listed:
  • Antoniou, Margarita
  • Sinha, Ankur
  • Papa, Gregor

Abstract

In this paper, we analyze a perturbed formulation of bilevel optimization problems, which we refer to as δ-perturbed formulation. The δ-perturbed formulation allows to handle the lower level optimization problem efficiently when there are multiple lower level optimal solutions. By using an appropriate perturbation strategy for the optimistic or pessimistic formulation, one can ensure that the optimization problem at the lower level contains only a single (approximate) optimal solution for any given decision at the upper level. The optimistic or the pessimistic bilevel optimal solution can then be efficiently searched for by algorithms that rely on solving the lower level optimization problem multiple times during the solution search procedure. The δ-perturbed formulation is arrived at by adding the upper level objective function to the lower level objective function after multiplying the upper level objective by a small positive/negative δ. We provide a proof that the δ-perturbed formulation is approximately equivalent to the original optimistic or pessimistic formulation and give an error bound for the approximation. We apply this scheme to a class of algorithms that attempts to solve optimistic and pessimistic variants of bilevel optimization problems by repeatedly solving the lower level optimization problem.

Suggested Citation

  • Antoniou, Margarita & Sinha, Ankur & Papa, Gregor, 2024. "δ-perturbation of bilevel optimization problems: An error bound analysis," Operations Research Perspectives, Elsevier, vol. 13(C).
  • Handle: RePEc:eee:oprepe:v:13:y:2024:i:c:s2214716024000198
    DOI: 10.1016/j.orp.2024.100315
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S2214716024000198
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.orp.2024.100315?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Miles G. Nicholls, 1995. "Aluminum Production Modeling—A Nonlinear Bilevel Programming Approach," Operations Research, INFORMS, vol. 43(2), pages 208-218, April.
    2. Martine Labbé & Patrice Marcotte & Gilles Savard, 1998. "A Bilevel Model of Taxation and Its Application to Optimal Highway Pricing," Management Science, INFORMS, vol. 44(12-Part-1), pages 1608-1622, December.
    3. Wayne F. Bialas & Mark H. Karwan, 1984. "Two-Level Linear Programming," Management Science, INFORMS, vol. 30(8), pages 1004-1020, August.
    4. Kalyanmoy Deb & Ankur Sinha & Pekka Malo & Zhichao Lu, 2020. "Approximate Bilevel Optimization with Population-Based Evolutionary Algorithms," Springer Optimization and Its Applications, in: Stephan Dempe & Alain Zemkoho (ed.), Bilevel Optimization, chapter 0, pages 361-402, Springer.
    5. June Liu & Yuxin Fan & Zhong Chen & Yue Zheng, 2020. "Methods for Pessimistic Bilevel Optimization," Springer Optimization and Its Applications, in: Stephan Dempe & Alain Zemkoho (ed.), Bilevel Optimization, chapter 0, pages 403-420, Springer.
    6. Shenglong Zhou & Alain B. Zemkoho & Andrey Tin, 2020. "BOLIB: Bilevel Optimization LIBrary of Test Problems," Springer Optimization and Its Applications, in: Stephan Dempe & Alain Zemkoho (ed.), Bilevel Optimization, chapter 0, pages 563-580, Springer.
    7. Jerome Bracken & James T. McGill, 1973. "Mathematical Programs with Optimization Problems in the Constraints," Operations Research, INFORMS, vol. 21(1), pages 37-44, February.
    8. Hecheng Li, 2015. "A genetic algorithm using a finite search space for solving nonlinear/linear fractional bilevel programming problems," Annals of Operations Research, Springer, vol. 235(1), pages 543-558, December.
    9. Beraldi, Patrizia, 2024. "Green retailer: A stochastic bi-level approach to support investment decisions in sustainable energy systems," Operations Research Perspectives, Elsevier, vol. 12(C).
    10. M. Beatrice Lignola & Jacqueline Morgan, 2017. "Inner Regularizations and Viscosity Solutions for Pessimistic Bilevel Optimization Problems," Journal of Optimization Theory and Applications, Springer, vol. 173(1), pages 183-202, April.
    11. Xinmin Hu & Daniel Ralph, 2007. "Using EPECs to Model Bilevel Games in Restructured Electricity Markets with Locational Prices," Operations Research, INFORMS, vol. 55(5), pages 809-827, October.
    12. Sinha, Ankur & Malo, Pekka & Deb, Kalyanmoy, 2017. "Evolutionary algorithm for bilevel optimization using approximations of the lower level optimal solution mapping," European Journal of Operational Research, Elsevier, vol. 257(2), pages 395-411.
    13. Benoît Colson & Patrice Marcotte & Gilles Savard, 2007. "An overview of bilevel optimization," Annals of Operations Research, Springer, vol. 153(1), pages 235-256, September.
    14. Cao, D. & Leung, L. C., 2002. "A partial cooperation model for non-unique linear two-level decision problems," European Journal of Operational Research, Elsevier, vol. 140(1), pages 134-141, July.
    15. Gerald Brown & Matthew Carlyle & Douglas Diehl & Jeffrey Kline & Kevin Wood, 2005. "A Two-Sided Optimization for Theater Ballistic Missile Defense," Operations Research, INFORMS, vol. 53(5), pages 745-763, October.
    16. Thomas Kleinert & Martin Schmidt, 2021. "Computing Feasible Points of Bilevel Problems with a Penalty Alternating Direction Method," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 198-215, January.
    17. Lawrence M. Wein, 2009. "OR Forum---Homeland Security: From Mathematical Models to Policy Implementation: The 2008 Philip McCord Morse Lecture," Operations Research, INFORMS, vol. 57(4), pages 801-811, August.
    18. Luce Brotcorne & Martine Labbé & Patrice Marcotte & Gilles Savard, 2001. "A Bilevel Model for Toll Optimization on a Multicommodity Transportation Network," Transportation Science, INFORMS, vol. 35(4), pages 345-358, November.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Ankur Sinha & Zhichao Lu & Kalyanmoy Deb & Pekka Malo, 2020. "Bilevel optimization based on iterative approximation of multiple mappings," Journal of Heuristics, Springer, vol. 26(2), pages 151-185, April.
    2. Bo Zeng, 2020. "A Practical Scheme to Compute the Pessimistic Bilevel Optimization Problem," INFORMS Journal on Computing, INFORMS, vol. 32(4), pages 1128-1142, October.
    3. Li, Ruijie & Liu, Yang & Liu, Xiaobo & Nie, Yu (Marco), 2024. "Allocation problem in cross-platform ride-hail integration," Transportation Research Part B: Methodological, Elsevier, vol. 188(C).
    4. Jayaswal, Sachin & Sinha, Ankur, 2022. "Bilevel Optimization: Applications, Models and Solution Approaches," IIMA Working Papers WP 2022-05-02, Indian Institute of Management Ahmedabad, Research and Publication Department.
    5. Beck, Yasmine & Ljubić, Ivana & Schmidt, Martin, 2023. "A survey on bilevel optimization under uncertainty," European Journal of Operational Research, Elsevier, vol. 311(2), pages 401-426.
    6. Thomas Kleinert & Martine Labbé & Fr¨ank Plein & Martin Schmidt, 2020. "Technical Note—There’s No Free Lunch: On the Hardness of Choosing a Correct Big-M in Bilevel Optimization," Operations Research, INFORMS, vol. 68(6), pages 1716-1721, November.
    7. Benoît Colson & Patrice Marcotte & Gilles Savard, 2007. "An overview of bilevel optimization," Annals of Operations Research, Springer, vol. 153(1), pages 235-256, September.
    8. Martine Labbé & Alessia Violin, 2016. "Bilevel programming and price setting problems," Annals of Operations Research, Springer, vol. 240(1), pages 141-169, May.
    9. R. Paulavičius & C. S. Adjiman, 2020. "New bounding schemes and algorithmic options for the Branch-and-Sandwich algorithm," Journal of Global Optimization, Springer, vol. 77(2), pages 197-225, June.
    10. Xi, Haoning & Aussel, Didier & Liu, Wei & Waller, S.Travis. & Rey, David, 2024. "Single-leader multi-follower games for the regulation of two-sided mobility-as-a-service markets," European Journal of Operational Research, Elsevier, vol. 317(3), pages 718-736.
    11. Budnitzki, Alina, 2014. "Computation of the optimal tolls on the traffic network," European Journal of Operational Research, Elsevier, vol. 235(1), pages 247-251.
    12. S. Dutta & S. Acharya, 2024. "A Novel Approach to Solve Multi-objective Fuzzy Stochastic Bilevel Programming Using Genetic Algorithm," SN Operations Research Forum, Springer, vol. 5(1), pages 1-24, March.
    13. Acuna, Jorge A. & Zayas-Castro, Jose L. & Feijoo, Felipe, 2022. "A bilevel Nash-in-Nash model for hospital mergers: A key to affordable care," Socio-Economic Planning Sciences, Elsevier, vol. 83(C).
    14. Christine Tawfik & Sabine Limbourg, 2019. "A Bilevel Model for Network Design and Pricing Based on a Level-of-Service Assessment," Transportation Science, INFORMS, vol. 53(6), pages 1609-1626, November.
    15. Yemshanov, Denys & Haight, Robert G. & MacQuarrie, Chris J.K. & Simpson, Mackenzie & Koch, Frank H. & Ryan, Kathleen & Bullas-Appleton, Erin, 2022. "Hierarchical governance in invasive species survey campaigns," Ecological Economics, Elsevier, vol. 201(C).
    16. Carlos Henggeler Antunes & Maria João Alves & Billur Ecer, 2020. "Bilevel optimization to deal with demand response in power grids: models, methods and challenges," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 28(3), pages 814-842, October.
    17. Ashenafi Woldemariam & Semu Kassa, 2015. "Systematic evolutionary algorithm for general multilevel Stackelberg problems with bounded decision variables (SEAMSP)," Annals of Operations Research, Springer, vol. 229(1), pages 771-790, June.
    18. Sinha, Ankur & Malo, Pekka & Deb, Kalyanmoy, 2017. "Evolutionary algorithm for bilevel optimization using approximations of the lower level optimal solution mapping," European Journal of Operational Research, Elsevier, vol. 257(2), pages 395-411.
    19. Çalcı, Baturay & Leibowicz, Benjamin D. & Bard, Jonathan F. & Jayadev, Gopika G., 2024. "A bilevel approach to multi-period natural gas pricing and investment in gas-consuming infrastructure," Energy, Elsevier, vol. 303(C).
    20. Yu-Wei Li & Gui-Hua Lin & Xide Zhu, 2024. "Solving Bilevel Programs Based on Lower-Level Mond-Weir Duality," INFORMS Journal on Computing, INFORMS, vol. 36(5), pages 1225-1241, September.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:oprepe:v:13:y:2024:i:c:s2214716024000198. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.journals.elsevier.com/operations-research-perspectives .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.