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 |
Volume | 71 |
Issue number | 5 |
Pages (from-to) | 846-865 |
ISSN | 0160-5682 |
DOIs | |
Publication status | Published - 2020 |
Keywords
- investment
- linear programming
- non-linear programming
- Optimisation