A parametric programming approach to bilevel optimisation with lower-level variables in the upper level

Henrik C. Bylling*, Steven A. Gabriel, Trine K. Boomsma

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

7 Citations (Scopus)
257 Downloads (Pure)

Abstract

This paper examines linearly constrained bilevel programming problems in which the upper-level objective function depends on both the lower-level primal and dual optimal solutions. We parametrize the lower-level solutions and thereby the upper-level objective function by the upper-level variables and argue that it may be non-convex and even discontinuous. However, when the upper-level objective is affine in the lower-level primal optimal solution, the parametric function is piece-wise linear. We show how this property facilitates the application of parametric programming and demonstrate how the approach allows for decomposition of a separable lower-level problem. When the upper-level objective is bilinear in the lower-level primal and dual optimal solutions, we also provide an exact linearisation method that reduces the bilevel problem to a single-level mixed-integer linear programme (MILP). We assess the performance of the parametric programming approach on two case studies of strategic investment in electricity markets and benchmark against state-of-the-art MILP and non-linear solution methods for bilevel optimisation problems. Preliminary results indicate substantial computational advantages over several standard solvers, especially when the lower-level problem separates into a large number of subproblems. Furthermore, we show that the parametric programming approach succeeds in solving problems to global optimality for which standard methods can fail.

Original languageEnglish
JournalJournal of the Operational Research Society
Volume71
Issue number5
Pages (from-to)846-865
ISSN0160-5682
DOIs
Publication statusPublished - 2020

Keywords

  • investment
  • linear programming
  • non-linear programming
  • Optimisation

Cite this