IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v32y4i2020p1128-1142.html
   My bibliography  Save this article

A Practical Scheme to Compute the Pessimistic Bilevel Optimization Problem

Author

Listed:
  • Bo Zeng

    (Department of Industrial Engineering, University of Pittsburgh, Pittsburgh, Pennsylvania 15261)

Abstract

In this paper, we present a new computation scheme for the pessimistic bilevel optimization problem, which so far does not have any computational methods generally applicable. We first develop a tight relaxation and then design a simple scheme to ensure a feasible and optimal solution. Then we discuss using this scheme to analyze and compute a linear pessimistic bilevel problem and several extensions. We also provide demonstrations on illustrative examples and a systematic numerical study on instances of two practical problems. Because of its simple structure and strong computational capacity, we believe that the developed scheme is of critical value in studying and solving pessimistic bilevel optimization problems arising from practice.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:orijoc:v:32:y:4:i:2020:p:1128-1142
    DOI: 10.1287/ijoc.2019.0927
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/ijoc.2019.0927
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2019.0927?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
    ---><---

    References listed on IDEAS

    as
    1. M. Beatrice Lignola & Jacqueline Morgan, 2012. "Approximating Security Values of MinSup Problems with Quasi-variational Inequality Constraints," CSEF Working Papers 321, Centre for Studies in Economics and Finance (CSEF), University of Naples, Italy, revised 09 Oct 2014.
    2. Jerome Bracken & James T. McGill, 1973. "Mathematical Programs with Optimization Problems in the Constraints," Operations Research, INFORMS, vol. 21(1), pages 37-44, February.
    3. Bard, Jonathan F. & Plummer, John & Claude Sourie, Jean, 2000. "A bilevel programming approach to determining tax credits for biofuel production," European Journal of Operational Research, Elsevier, vol. 120(1), pages 30-46, January.
    4. T. L. Magnanti & R. T. Wong, 1981. "Accelerating Benders Decomposition: Algorithmic Enhancement and Model Selection Criteria," Operations Research, INFORMS, vol. 29(3), pages 464-484, June.
    5. 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.
    6. 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.
    7. Nair, Rahul & Miller-Hooks, Elise, 2014. "Equilibrium network design of shared-vehicle systems," European Journal of Operational Research, Elsevier, vol. 235(1), pages 47-61.
    8. Wayne F. Bialas & Mark H. Karwan, 1984. "Two-Level Linear Programming," Management Science, INFORMS, vol. 30(8), pages 1004-1020, August.
    9. C. Audet & P. Hansen & B. Jaumard & G. Savard, 1997. "Links Between Linear Bilevel and Mixed 0–1 Programming Problems," Journal of Optimization Theory and Applications, Springer, vol. 93(2), pages 273-300, May.
    10. Luce Brotcorne & Martine Labbé & Patrice Marcotte & Gilles Savard, 2008. "Joint Design and Pricing on a Network," Operations Research, INFORMS, vol. 56(5), pages 1104-1115, October.
    11. M. Köppe & M. Queyranne & C. T. Ryan, 2010. "Parametric Integer Programming Algorithm for Bilevel Mixed Integer Programs," Journal of Optimization Theory and Applications, Springer, vol. 146(1), pages 137-150, July.
    12. 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.
    13. 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.
    14. R. G. Cassidy & M. J. L. Kirby & W. M. Raike, 1971. "Efficient Distribution of Resources Through Three Levels of Government," Management Science, INFORMS, vol. 17(8), pages 462-473, April.
    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. 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.
    2. Junlong Zhang & Osman Y. Özaltın, 2021. "Bilevel Integer Programs with Stochastic Right-Hand Sides," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1644-1660, October.
    3. Tamás Kis & András Kovács & Csaba Mészáros, 2021. "On Optimistic and Pessimistic Bilevel Optimization Models for Demand Response Management," Energies, MDPI, vol. 14(8), pages 1-22, April.

    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. 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.
    2. Mofidi, Seyed Shahab & Pazour, Jennifer A., 2019. "When is it beneficial to provide freelance suppliers with choice? A hierarchical approach for peer-to-peer logistics platforms," Transportation Research Part B: Methodological, Elsevier, vol. 126(C), pages 1-23.
    3. M. Hosein Zare & Osman Y. Özaltın & Oleg A. Prokopyev, 2018. "On a class of bilevel linear mixed-integer programs in adversarial settings," Journal of Global Optimization, Springer, vol. 71(1), pages 91-113, May.
    4. 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).
    5. 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.
    6. M. Hosein Zare & Oleg A. Prokopyev & Denis Sauré, 2020. "On Bilevel Optimization with Inexact Follower," Decision Analysis, INFORMS, vol. 17(1), pages 74-95, March.
    7. Martine Labbé & Alessia Violin, 2016. "Bilevel programming and price setting problems," Annals of Operations Research, Springer, vol. 240(1), pages 141-169, May.
    8. Junlong Zhang & Osman Y. Özaltın, 2021. "Bilevel Integer Programs with Stochastic Right-Hand Sides," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1644-1660, October.
    9. Cao, Dong & Chen, Mingyuan, 2006. "Capacitated plant selection in a decentralized manufacturing environment: A bilevel optimization approach," European Journal of Operational Research, Elsevier, vol. 169(1), pages 97-110, February.
    10. Nair, Rahul & Miller-Hooks, Elise, 2014. "Equilibrium network design of shared-vehicle systems," European Journal of Operational Research, Elsevier, vol. 235(1), pages 47-61.
    11. Juan S. Borrero & Oleg A. Prokopyev & Denis Sauré, 2019. "Sequential Interdiction with Incomplete Information and Learning," Operations Research, INFORMS, vol. 67(1), pages 72-89, January.
    12. 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.
    13. 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.
    14. Matteo Fischetti & Ivana Ljubić & Michele Monaci & Markus Sinnl, 2017. "A New General-Purpose Algorithm for Mixed-Integer Bilevel Linear Programs," Operations Research, INFORMS, vol. 65(6), pages 1615-1637, December.
    15. 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.
    16. Ç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).
    17. 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.
    18. Polyxeni-Margarita Kleniati & Claire Adjiman, 2014. "Branch-and-Sandwich: a deterministic global optimization algorithm for optimistic bilevel programming problems. Part I: Theoretical development," Journal of Global Optimization, Springer, vol. 60(3), pages 425-458, November.
    19. Rahul Nair & Elise Miller-Hooks, 2016. "Equilibrium design of bicycle sharing systems: the case of Washington D.C," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 5(3), pages 321-344, August.
    20. Gabriel Lopez Zenarosa & Oleg A. Prokopyev & Eduardo L. Pasiliao, 2021. "On exact solution approaches for bilevel quadratic 0–1 knapsack problem," Annals of Operations Research, Springer, vol. 298(1), pages 555-572, March.

    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:inm:orijoc:v:32:y:4:i:2020:p:1128-1142. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.