Globally solving a class of bilevel programs with spatial price equilibrium constraints

Research output: Contribution to journalArticlepeer-review

Abstract

Bilevel programs with spatial price equilibrium constraints are strategic models that consider a price competition at the lower level. These models find application in facility location-price models, optimal bidding in power networks, and integration of renewable energy sources in distribution networks. In this paper, for the case where the equilibrium at the lower level can be formulated as an optimization problem, we introduce an enhanced single-level formulation based on duality and show that its relaxation is stronger than the single-level formulation obtained using KKT conditions. Compared to the literature Friesz et al. (Environ Plann B Plann Des 15(2):191–203, 1988), Miller et al. (Ann Oper Res 34(1):177–202, 1992), this new formulation (i) is computationally friendly to global solution strategies using branch-and-bound, and (ii) can tackle instances of larger size. Further, we develop a heuristic procedure to find feasible solutions inside of the branch-and-bound tree that is effective on instances of large size and produces solutions whose objective values are close to the relaxation bound. We demonstrate the benefits of this formulation and heuristic through an extensive numerical study on synthetic instances of equilibrium facility location Miller et al. (Equilibrium Facility Location on Networks. Springer, Berlin 1995) and on standard IEEE bus networks for planning renewable generation capacity under uncertainty.

Original languageEnglish (US)
JournalOptimization Letters
DOIs
StateAccepted/In press - 2024
Externally publishedYes

Bibliographical note

Publisher Copyright:
© The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature 2024.

Keywords

  • Bilevel optimization
  • Facility location
  • Renewable generation unit
  • Spatial price equilibrium

Fingerprint

Dive into the research topics of 'Globally solving a class of bilevel programs with spatial price equilibrium constraints'. Together they form a unique fingerprint.

Cite this