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

Research output: Contribution to journalJournal articlepeer-review

Standard

A parametric programming approach to bilevel optimisation with lower-level variables in the upper level. / Bylling, Henrik C.; Gabriel, Steven A.; Boomsma, Trine K.

In: Journal of the Operational Research Society, Vol. 71, No. 5, 2020, p. 846-865.

Research output: Contribution to journalJournal articlepeer-review

Harvard

Bylling, HC, Gabriel, SA & Boomsma, TK 2020, 'A parametric programming approach to bilevel optimisation with lower-level variables in the upper level', Journal of the Operational Research Society, vol. 71, no. 5, pp. 846-865. https://doi.org/10.1080/01605682.2019.1590132

APA

Bylling, H. C., Gabriel, S. A., & Boomsma, T. K. (2020). A parametric programming approach to bilevel optimisation with lower-level variables in the upper level. Journal of the Operational Research Society, 71(5), 846-865. https://doi.org/10.1080/01605682.2019.1590132

Vancouver

Bylling HC, Gabriel SA, Boomsma TK. A parametric programming approach to bilevel optimisation with lower-level variables in the upper level. Journal of the Operational Research Society. 2020;71(5):846-865. https://doi.org/10.1080/01605682.2019.1590132

Author

Bylling, Henrik C. ; Gabriel, Steven A. ; Boomsma, Trine K. / A parametric programming approach to bilevel optimisation with lower-level variables in the upper level. In: Journal of the Operational Research Society. 2020 ; Vol. 71, No. 5. pp. 846-865.

Bibtex

@article{4b5d9d4da52c4447bd33c2ea7d144fae,
title = "A parametric programming approach to bilevel optimisation with lower-level variables in the upper level",
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.",
keywords = "investment, linear programming, non-linear programming, Optimisation",
author = "Bylling, {Henrik C.} and Gabriel, {Steven A.} and Boomsma, {Trine K.}",
year = "2020",
doi = "10.1080/01605682.2019.1590132",
language = "English",
volume = "71",
pages = "846--865",
journal = "Journal of the Operational Research Society",
issn = "0160-5682",
publisher = "Palgrave Macmillan",
number = "5",

}

RIS

TY - JOUR

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

AU - Bylling, Henrik C.

AU - Gabriel, Steven A.

AU - Boomsma, Trine K.

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

KW - investment

KW - linear programming

KW - non-linear programming

KW - Optimisation

U2 - 10.1080/01605682.2019.1590132

DO - 10.1080/01605682.2019.1590132

M3 - Journal article

AN - SCOPUS:85066796293

VL - 71

SP - 846

EP - 865

JO - Journal of the Operational Research Society

JF - Journal of the Operational Research Society

SN - 0160-5682

IS - 5

ER -

ID: 223822722