A parametric programming approach to bilevel optimisation with lower-level variables in the upper level
Research output: Contribution to journal › Journal article › Research › peer-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 journal › Journal article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
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