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 language | English |
|---|---|
| Journal | Journal of the Operational Research Society |
| ISSN | 0160-5682 |
| DOIs | |
| Publication status | Published - 3 May 2020 |
Keywords
- investment
- linear programming
- non-linear programming
- Optimisation