A Subgradient Technique for Resource Management in Electricity Networks

Samuel Zürcher, Master Thesis, Spring 2009

Supervisors: Michael Guarisco, Marco Laumanns

The regulation schemes for grid fees in liberalized electricity markets give strong incentives to power grid operators for cost reduction. As the attempt to reduce operating costs may have negative effects on the quality of supply, regulators impose quality standards. Accordingly, grid operators try to find an optimal balance between costs and quality of supply. One main aspect of the quality of supply concerns the availability of electricity to customers. The restoration process after incidents in the power grid depends on the availability of (human) resources. For incidents with an interruption of supply, a temporary non-availability of resources delays the restoration and hence directly influences the quality of supply. However, due to the redundancies and the degree of automation and remote control, particularly in the high- and extra-high-voltage power grid, not every incident entails an interruption of supply. Nonetheless, the failed equipment generally needs to be repaired. As the redundancy is reduced after an incident, a delay in the repair directly affects the duration of the grid being in a status of risk. Additional incidents might eventually lead to a (large) interruption of supply.

In this project, a power supply system is considered that consists of a power grid (power supply lines, transformers, etc.), consumers/loads, and (human) resources. Due to technical failures or external causes, the electrical equipment can fail and thus has to be repaired by the resources. The relation between a given number of resources and the corresponding quality of supply is analyzed by a state-based stochastic dynamic optimization model, namely by an average cost per stage Markov decision process. The cost in this setting is intended to measure the quality of supply and is defined as the energy not supplied. The state of the system at a given point in time is defined by the state of the power grid and the allocation of the resources. The system is assumed to be stationary and is considered in discrete time steps over an infinite time horizon. For a given number of resources, the aim of the model is to find a policy with minimum average cost (i.e., minimum expected energy not supplied) per time step. The optimal average cost for different numbers of resources may be used to support strategic decisions in resource management.

There are several methods to solve this type of Markov decision process based on value iteration, policy iteration, or linear programming. The validity of these methods depends on structural assumptions about the underlying Markov chains. One main difficulty of the described model is that the number of states is very large (exponential in the number of components of the power grid) and hence approximate solution methods are needed. The first goal of this work was to formulate conditions on the model which assure the desired structural assumptions. The second goal was to analyze and implement a subgradient method of Nesterov to solve the Lagrange dual of the linear program. The third goal was to solve and analyze examples based on real-world data and compare the subgradient method and the value iteration method.

In the first part of the work, a set of assumptions were motivated to reduce the number of states and policies in the model. Additional conditions were formulated to assure the desired structural properties, e.g., that the optimal average cost is independent of the initial state of the system. To assess the energy not supplied (i.e., the cost) for each state, a load shedding model based on the DC power flow equations was formulated. Then, the subgradient method was studied and adapted to the given setting. Several properties of approximately optimal solutions of the Lagrange dual problem were derived. To implement the method, a procedure to generate the states and controls (policies) had to be developed. Moreover, a restarting procedure was suggested to speed up the algorithm. Finally, in a case study with real world data, the subgradient method and a modified version of the value iteration method were contrasted and the results for different failure scenarios (average weather, storm, thunderstorm) were investigated. The computational results showed that the subgradient method converges much slower than the value iteration method. The optimal average cost in the case study is close to its minimum already for few resources, which is consistent with the small probability of simultaneous failures and the redundancies in the power grid.