IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v77y2020i2d10.1007_s10898-020-00874-3.html
   My bibliography  Save this article

New bounding schemes and algorithmic options for the Branch-and-Sandwich algorithm

Author

Listed:
  • R. Paulavičius

    (Imperial College London
    Vilnius University Institute of Data Science and Digital Technologies)

  • C. S. Adjiman

    (Imperial College London)

Abstract

We consider the global solution of bilevel programs involving nonconvex functions. Deterministic global optimization algorithms for the solution of this challenging class of optimization problems have started to emerge over the last few years. We present new schemes to generate valid bounds on the solution of nonconvex inner and outer problems and examine new strategies for branching and node selection. We integrate these within the Branch-and-Sandwich algorithm (Kleniati and Adjiman in J Glob Opt 60:425–458, 2014), which is based on a branch-and-bound framework and enables the solution of a wide range of problems, including those with nonconvex inequalities and equalities in the inner problem. The impact of the proposed modifications is demonstrated on an illustrative example and 10 nonconvex bilevel test problems from the literature. It is found that the performance of the algorithm is improved for all but one problem (where the CPU time is increased by 2%), with an average reduction in CPU time of 39%. For the two most challenging problems, the CPU time required is decreased by factors of over 3 and 10.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:jglopt:v:77:y:2020:i:2:d:10.1007_s10898-020-00874-3
    DOI: 10.1007/s10898-020-00874-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-020-00874-3
    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/s10898-020-00874-3?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. Casas-Ramírez, Martha-Selene & Camacho-Vallejo, José-Fernando & Martínez-Salazar, Iris-Abril, 2018. "Approximating solutions to a bilevel capacitated facility location problem with customer's patronization toward a list of preferences," Applied Mathematics and Computation, Elsevier, vol. 319(C), pages 369-386.
    2. Calvete, Herminia I. & Gale, Carmen & Mateo, Pedro M., 2008. "A new approach for solving linear bilevel problems using genetic algorithms," European Journal of Operational Research, Elsevier, vol. 188(1), pages 14-28, July.
    3. Stein, Oliver & Still, Georg, 2002. "On generalized semi-infinite optimization and bilevel optimization," European Journal of Operational Research, Elsevier, vol. 142(3), pages 444-462, November.
    4. 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.
    5. 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.
    6. 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.
    7. Cecchini, Mark & Ecker, Joseph & Kupferschmid, Michael & Leitch, Robert, 2013. "Solving nonlinear principal-agent problems using bilevel programming," European Journal of Operational Research, Elsevier, vol. 230(2), pages 364-373.
    8. Polyxeni-M. Kleniati & Claire Adjiman, 2014. "Branch-and-Sandwich: a deterministic global optimization algorithm for optimistic bilevel programming problems. Part II: Convergence analysis and numerical results," Journal of Global Optimization, Springer, vol. 60(3), pages 459-481, November.
    9. 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.
    10. Hatim Djelassi & Moll Glass & Alexander Mitsos, 2019. "Discretization-based algorithms for generalized semi-infinite and bilevel programs with coupling equality constraints," Journal of Global Optimization, Springer, vol. 75(2), pages 341-392, October.
    11. Calvete, Herminia I. & Gale, Carmen, 1999. "The bilevel linear/linear fractional programming problem," European Journal of Operational Research, Elsevier, vol. 114(1), pages 188-197, April.
    12. Jerome Bracken & James T. McGill, 1973. "Mathematical Programs with Optimization Problems in the Constraints," Operations Research, INFORMS, vol. 21(1), pages 37-44, February.
    13. James T. Moore & Jonathan F. Bard, 1990. "The Mixed Integer Linear Bilevel Programming Problem," Operations Research, INFORMS, vol. 38(5), pages 911-921, October.
    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. Yasmine Beck & Daniel Bienstock & Martin Schmidt & Johannes Thürauf, 2023. "On a Computationally Ill-Behaved Bilevel Problem with a Continuous and Nonconvex Lower Level," Journal of Optimization Theory and Applications, Springer, vol. 198(1), pages 428-447, July.
    2. Maximilian Merkert & Galina Orlinskaya & Dieter Weninger, 2022. "An exact projection-based algorithm for bilevel mixed-integer problems with nonlinearities," Journal of Global Optimization, Springer, vol. 84(3), pages 607-650, November.

    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. Dajun Yue & Jiyao Gao & Bo Zeng & Fengqi You, 2019. "A projection-based reformulation and decomposition algorithm for global optimization of a class of mixed integer bilevel linear programs," Journal of Global Optimization, Springer, vol. 73(1), pages 27-57, January.
    2. Hatim Djelassi & Moll Glass & Alexander Mitsos, 2019. "Discretization-based algorithms for generalized semi-infinite and bilevel programs with coupling equality constraints," Journal of Global Optimization, Springer, vol. 75(2), pages 341-392, October.
    3. Maximilian Merkert & Galina Orlinskaya & Dieter Weninger, 2022. "An exact projection-based algorithm for bilevel mixed-integer problems with nonlinearities," Journal of Global Optimization, Springer, vol. 84(3), pages 607-650, November.
    4. Lei Fang & Hecheng Li, 2013. "Lower bound of cost efficiency measure in DEA with incomplete price information," Journal of Productivity Analysis, Springer, vol. 40(2), pages 219-226, October.
    5. Yasmine Beck & Daniel Bienstock & Martin Schmidt & Johannes Thürauf, 2023. "On a Computationally Ill-Behaved Bilevel Problem with a Continuous and Nonconvex Lower Level," Journal of Optimization Theory and Applications, Springer, vol. 198(1), pages 428-447, July.
    6. Richard Oberdieck & Nikolaos A. Diangelakis & Styliani Avraamidou & Efstratios N. Pistikopoulos, 2017. "On unbounded and binary parameters in multi-parametric programming: applications to mixed-integer bilevel optimization and duality theory," Journal of Global Optimization, Springer, vol. 69(3), pages 587-606, November.
    7. Fischetti, Matteo & Monaci, Michele & Sinnl, Markus, 2018. "A dynamic reformulation heuristic for Generalized Interdiction Problems," European Journal of Operational Research, Elsevier, vol. 267(1), pages 40-51.
    8. 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.
    9. Florensa, Carlos & Garcia-Herreros, Pablo & Misra, Pratik & Arslan, Erdem & Mehta, Sanjay & Grossmann, Ignacio E., 2017. "Capacity planning with competitive decision-makers: Trilevel MILP formulation, degeneracy, and solution approaches," European Journal of Operational Research, Elsevier, vol. 262(2), pages 449-463.
    10. 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.
    11. 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.
    12. 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.
    13. Cerulli, Martina & Serra, Domenico & Sorgente, Carmine & Archetti, Claudia & Ljubić, Ivana, 2023. "Mathematical programming formulations for the Collapsed k-Core Problem," European Journal of Operational Research, Elsevier, vol. 311(1), pages 56-72.
    14. 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.
    15. Jörg Fliege & Andrey Tin & Alain Zemkoho, 2021. "Gauss–Newton-type methods for bilevel optimization," Computational Optimization and Applications, Springer, vol. 78(3), pages 793-824, April.
    16. Küçükaydin, Hande & Aras, Necati & Kuban AltInel, I., 2011. "Competitive facility location problem with attractiveness adjustment of the follower: A bilevel programming model and its solution," European Journal of Operational Research, Elsevier, vol. 208(3), pages 206-220, February.
    17. S. Dempe & S. Franke, 2016. "On the solution of convex bilevel optimization problems," Computational Optimization and Applications, Springer, vol. 63(3), pages 685-703, April.
    18. Moon, Kyungduk & Lee, Kangbok & Chopra, Sunil & Kwon, Steve, 2022. "Bilevel integer programming on a Boolean network for discovering critical genetic alterations in cancer development and therapy," European Journal of Operational Research, Elsevier, vol. 300(2), pages 743-754.
    19. Onur Tavaslıoğlu & Oleg A. Prokopyev & Andrew J. Schaefer, 2019. "Solving Stochastic and Bilevel Mixed-Integer Programs via a Generalized Value Function," Operations Research, INFORMS, vol. 67(6), pages 1659-1677, November.
    20. 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.

    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:jglopt:v:77:y:2020:i:2:d:10.1007_s10898-020-00874-3. 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.