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:

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

Acknowledgements

The authors wish to thank two anonymous reviewers for their very useful comments and suggestions, which contributed significantly to improving this paper. Furthermore, T. K. Boomsma acknowledges support from the project AHEAD, Analyses of Hourly Electricity Demand, funded by Energiteknologisk Udviklings-og Demonstrationsprogram (EUDP) under the Danish Energy Agency.

Disclosure statement

No potential conflict of interest was reported by the authors.