Transmission Expansion Planning by Quantum Annealing

Abstract

The transmission expansion planning problem (TEP) can be formulated as a mixed-integer linearcprogramming (MILP) problem that aims at finding the optimal way to expand the capacity of an energy system. The solution provides the optimal layout of transmission lines that are to be built in order to satisfy the energy demand on a distributed energy system with a high share of renewable energy sources. The TEP scales badly using classical algorithms and, at the same time, energy system models are getting larger and more complex due to the integration of decentralized weather-dependent renewable energy sources, sector coupling and the increase of storage components. Currently, the problem is often linearized or the scope and granularity of the model are reduced using clustering algorithms. For this reason, any computational time reduction will have substantial implications in closing the granularity gap between what the current models can solve and the desired resolution needed by energy system operators. Quantum annealers are single-purpose quantum computers specialized in solving combinatorial optimization problems. Since quantum computers are still not sufficiently mature, large problems cannot be tackled purely with a quantum computer. We propose a decomposition protocol for the TEP problem which is similar in spirit to Benders decomposition algorithm, which allows us to use a hybrid quantum-classical approach to tackle bigger problems by providing the binary master problem to a quantum annealer and a set of slave sub-problems to classical solvers. Therefore, our method can take advantage of cutting-edge classical algorithms and current quantum annealers. The ultimate goal is to find solutions that are closer to the optimum while achieving a speed-up.