IDEAS home Printed from https://ideas.repec.org/a/spr/joheur/v26y2020i2d10.1007_s10732-019-09426-9.html
   My bibliography  Save this article

Bilevel optimization based on iterative approximation of multiple mappings

Author

Listed:
  • Ankur Sinha

    (Indian Institute of Management)

  • Zhichao Lu

    (Michigan State University)

  • Kalyanmoy Deb

    (Michigan State University)

  • Pekka Malo

    (Aalto University School of Economics)

Abstract

A large number of application problems involve two levels of optimization, where one optimization task is nested inside the other. These problems are known as bilevel optimization problems and have been studied by both classical optimization community and evolutionary optimization community. Most of the solution procedures proposed until now are either computationally very expensive or applicable to only small classes of bilevel optimization problems adhering to mathematically simplifying assumptions. In this paper, we propose an evolutionary optimization method that tries to reduce the computational expense by iteratively approximating two important mappings in bilevel optimization; namely, the lower level rational reaction mapping and the lower level optimal value function mapping. The algorithm has been tested on a large number of test problems and comparisons have been performed with other algorithms. The results show the performance gain to be quite significant. To the best knowledge of the authors, a combined theory-based and population-based solution procedure utilizing mappings has not been suggested yet for bilevel problems.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:joheur:v:26:y:2020:i:2:d:10.1007_s10732-019-09426-9
    DOI: 10.1007/s10732-019-09426-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10732-019-09426-9
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10732-019-09426-9?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. Jerome Bracken & James T. McGill, 1974. "Defense Applications of Mathematical Programs with Optimization Problems in the Constraints," Operations Research, INFORMS, vol. 22(5), pages 1086-1096, October.
    4. Jerome Bracken & James T. McGill, 1973. "Mathematical Programs with Optimization Problems in the Constraints," Operations Research, INFORMS, vol. 21(1), pages 37-44, February.
    5. 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.
    6. J. A. Mirrlees, 1999. "The Theory of Moral Hazard and Unobservable Behaviour: Part I," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 66(1), pages 3-21.
    7. 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.
    8. Bo An & Fernando Ordóñez & Milind Tambe & Eric Shieh & Rong Yang & Craig Baldwin & Joseph DiRenzo & Kathryn Moretti & Ben Maule & Garrett Meyer, 2013. "A Deployed Quantal Response-Based Patrol Planning System for the U.S. Coast Guard," Interfaces, INFORMS, vol. 43(5), pages 400-420, October.
    9. 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.
    10. Yuping Wang & Hong Li & Chuangyin Dang, 2011. "A New Evolutionary Algorithm for a Class of Nonlinear Bilevel Programming Problems and Its Global Convergence," INFORMS Journal on Computing, INFORMS, vol. 23(4), pages 618-629, November.
    11. 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.
    12. Nathan Williams & P. K. Kannan & Shapour Azarm, 2011. "Retail Channel Structure Impact on Strategic Engineering Product Design," Management Science, INFORMS, vol. 57(5), pages 897-914, May.
    13. 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)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. 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.
    2. Mejía-de-Dios, Jesús-Adolfo & Mezura-Montes, Efrén & Toledo-Hernández, Porfirio, 2022. "Pseudo-feasible solutions in evolutionary bilevel optimization: Test problems and performance assessment," Applied Mathematics and Computation, Elsevier, vol. 412(C).
    3. Rihab Said & Maha Elarbi & Slim Bechikh & Lamjed Ben Said, 2022. "Solving combinatorial bi-level optimization problems using multiple populations and migration schemes," Operational Research, Springer, vol. 22(3), pages 1697-1735, July.

    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. Antoniou, Margarita & Sinha, Ankur & Papa, Gregor, 2024. "δ-perturbation of bilevel optimization problems: An error bound analysis," Operations Research Perspectives, Elsevier, vol. 13(C).
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    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. Ç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).
    8. Tawfik, Christine & Gendron, Bernard & Limbourg, Sabine, 2022. "An iterative two-stage heuristic algorithm for a bilevel service network design and pricing model," European Journal of Operational Research, Elsevier, vol. 300(2), pages 512-526.
    9. Martine Labbé & Alessia Violin, 2016. "Bilevel programming and price setting problems," Annals of Operations Research, Springer, vol. 240(1), pages 141-169, May.
    10. 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.
    11. 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.
    12. Yanikoglu, I., 2014. "Robust optimization methods for chance constrained, simulation-based, and bilevel problems," Other publications TiSEM 45826f7e-6e21-481e-889e-4, Tilburg University, School of Economics and Management.
    13. 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.
    14. Ke, Ginger Y. & Zhang, Huiwen & Bookbinder, James H., 2020. "A dual toll policy for maintaining risk equity in hazardous materials transportation with fuzzy incident rate," International Journal of Production Economics, Elsevier, vol. 227(C).
    15. Mustapha Bouhtou & Stan van Hoesel & Anton F. van der Kraaij & Jean-Luc Lutton, 2007. "Tariff Optimization in Networks," INFORMS Journal on Computing, INFORMS, vol. 19(3), pages 458-469, August.
    16. Wang, Zhenjie & Zhang, Dezhi & Tavasszy, Lóránt & Fazi, Stefano, 2023. "Integrated multimodal freight service network design and pricing with a competing service integrator and heterogeneous shipper classes," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 179(C).
    17. 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).
    18. Joaquim Dias Garcia & Guilherme Bodin & Alexandre Street, 2024. "BilevelJuMP.jl: Modeling and Solving Bilevel Optimization Problems in Julia," INFORMS Journal on Computing, INFORMS, vol. 36(2), pages 327-335, March.
    19. van Hoesel, Stan, 2008. "An overview of Stackelberg pricing in networks," European Journal of Operational Research, Elsevier, vol. 189(3), pages 1393-1402, September.
    20. José Correa & Tobias Harks & Vincent J. C. Kreuzen & Jannik Matuschke, 2017. "Fare Evasion in Transit Networks," Operations Research, INFORMS, vol. 65(1), pages 165-183, February.

    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:spr:joheur:v:26:y:2020:i:2:d:10.1007_s10732-019-09426-9. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.