TY - BOOK

T1 - Bilevel Optimization with Applications in Energy

AU - Bylling, Henrik Carøe

PY - 2018

Y1 - 2018

N2 - Bilevel optimization problems are very applicable to economic models in general and in energy in particular. However, they are theoretically NP-hard and, thus, solving them implies a large computational burden. This thesis tries to overcome the computational burden of bilevel optimization models, particularly in energy models. Hence, it allows for implementation of long-term strategic problems.The thesis consists of five chapters. The first is an introduct ion to the methodologies of optimization and background of the energy market. It is followed by four self-contained chapters. The second chapter Efficiently solving Linear Bilevel Programming Problems using Off-the-shelf Optimization Software provides an overview of existing state-of-the-art solution methods to bilevel optimization methods. Furthermore it presents a new method to linear bilevel optimization problems based on a reformulation to mathematical programs with equilibrium constraints (MPEC). First, a regularization method is used to solve the MPEC using an off-the-shelf, non-linear solver to find a local optimal solution. Local optimal information is then used to reduce the computational burden of solving a mixedinteger reformulation of the MPEC to global optimality using off-the-shelf mixed-integer solvers. Extensive numerical studies are presented using a wide range of randomly generated examples. The results show that our method outperforms existing state-of-the-art methods in terms of computational burden and global optimality. The third chapter The Impact of Short-term Variability and Uncertainty on Long-Term Power Planning considers specific long-term models in power planning. This chapter investigates methods for aggregating data and reducing model size to obtain tractable yet close-to-optimal investment planning decisions. We consider including short-term variability and/or uncertainty and analyze under which circumstances these effects are relevant. In particular, we consider a generation expansion problem and compare various representations of short-term variability and uncertainty of demand and renewable supply.Numerical results are derived from a case study on the Danish power system. Our analysis shows that the inclusion of representative days is crucial for the feasibility and quality of long-term power planning decisions. The fourth chapter A Parametric Programming Approach to Bilevel Optimization with lower-level Variables in the upper Level examines linearly constrained bilevel programming problems in which the upper-level objective function depends on both the lowerlevel primal and dual optimal solutions. We argue that a parametrized upper-level objective 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 affine. 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 linearization method that reduces to a singlevi level mixed-integer linear programming (MILP) formulation of the bilevel problem. We present two numerical case studies of strategic investment in electricity markets and we benchmark the proposed method against state-of-the-art MILP and non-linear solution methods for bilevel optimization problems. Results indicate computational advantages over several standard solvers. We furthermore show that the parametric programming approach succeeds in solving problems to global optimality for which standard methods can The fifth chapter A Parametric Programming Approach to Bilevel Transmission Investment Problems in Power is an extension of Chapter 4 where the proposed parametric programming method is applied to a transmission investment problem. Specifically, we formulate the stochastic transmission expansion problem of a merchant investor collecting congestion rents that are determined by the differences between nodal market prices. The corresponding bilevel program can be recast as an MPEC, but does not allow for linearization and reformulation by mixed-integer linear programming. Instead, the parametric programming approach from chapter 4 is adapted to handle binary upper-level variables

AB - Bilevel optimization problems are very applicable to economic models in general and in energy in particular. However, they are theoretically NP-hard and, thus, solving them implies a large computational burden. This thesis tries to overcome the computational burden of bilevel optimization models, particularly in energy models. Hence, it allows for implementation of long-term strategic problems.The thesis consists of five chapters. The first is an introduct ion to the methodologies of optimization and background of the energy market. It is followed by four self-contained chapters. The second chapter Efficiently solving Linear Bilevel Programming Problems using Off-the-shelf Optimization Software provides an overview of existing state-of-the-art solution methods to bilevel optimization methods. Furthermore it presents a new method to linear bilevel optimization problems based on a reformulation to mathematical programs with equilibrium constraints (MPEC). First, a regularization method is used to solve the MPEC using an off-the-shelf, non-linear solver to find a local optimal solution. Local optimal information is then used to reduce the computational burden of solving a mixedinteger reformulation of the MPEC to global optimality using off-the-shelf mixed-integer solvers. Extensive numerical studies are presented using a wide range of randomly generated examples. The results show that our method outperforms existing state-of-the-art methods in terms of computational burden and global optimality. The third chapter The Impact of Short-term Variability and Uncertainty on Long-Term Power Planning considers specific long-term models in power planning. This chapter investigates methods for aggregating data and reducing model size to obtain tractable yet close-to-optimal investment planning decisions. We consider including short-term variability and/or uncertainty and analyze under which circumstances these effects are relevant. In particular, we consider a generation expansion problem and compare various representations of short-term variability and uncertainty of demand and renewable supply.Numerical results are derived from a case study on the Danish power system. Our analysis shows that the inclusion of representative days is crucial for the feasibility and quality of long-term power planning decisions. The fourth chapter A Parametric Programming Approach to Bilevel Optimization with lower-level Variables in the upper Level examines linearly constrained bilevel programming problems in which the upper-level objective function depends on both the lowerlevel primal and dual optimal solutions. We argue that a parametrized upper-level objective 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 affine. 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 linearization method that reduces to a singlevi level mixed-integer linear programming (MILP) formulation of the bilevel problem. We present two numerical case studies of strategic investment in electricity markets and we benchmark the proposed method against state-of-the-art MILP and non-linear solution methods for bilevel optimization problems. Results indicate computational advantages over several standard solvers. We furthermore show that the parametric programming approach succeeds in solving problems to global optimality for which standard methods can The fifth chapter A Parametric Programming Approach to Bilevel Transmission Investment Problems in Power is an extension of Chapter 4 where the proposed parametric programming method is applied to a transmission investment problem. Specifically, we formulate the stochastic transmission expansion problem of a merchant investor collecting congestion rents that are determined by the differences between nodal market prices. The corresponding bilevel program can be recast as an MPEC, but does not allow for linearization and reformulation by mixed-integer linear programming. Instead, the parametric programming approach from chapter 4 is adapted to handle binary upper-level variables

UR - https://soeg.kb.dk/permalink/45KBDK_KGL/1pioq0f/alma99123531260105763

M3 - Ph.D. thesis

BT - Bilevel Optimization with Applications in Energy

PB - Department of Mathematical Sciences, Faculty of Science, University of Copenhagen

ER -