A stochastic mathematical program with complementary constraints for market-wide power generation and transmission expansion planning

In the restructured electricity markets, the generators and the Independent System Operator (ISO) play important roles in the balance of electricity supply and demand. We consider a mixed integer bi-level model reformulated as a mathematical program with complementary constraints (MPCC) in which a single conceptual leader decides the transmission line expansion plan and generators plan for generation capacity expansion in the upper level. The overall objective is to maximize the total social welfare, which consists of buyer surplus, producer surplus and transmission rents. In the lower level, generators will maximize their operational profits by interaction with the ISO to decide their generation amounts. Meanwhile, the lower-level objective of the ISO is to maximize the social welfare by dispatching the electricity to satisfy demand and set the locational marginal prices (LMPs). Reformulating the complementarity constraints with binary variables results in a mixed integer program that can be solved to global optimality. However in reality, the demand and fuel cost will fluctuate with uncertainties such as climate change or natural resource limitations. A moment matching method for scenario generation can capture the uncertainties by producing a scenario tree. Then we combine the scenario tree with the mixed integer program to obtain a two-stage stochastic program where the first stage corresponds to the upper level investment decisions and the second stage represents the lower level operations. The extensive form of the stochastic program cannot be solved in our numerical example within a reasonable time limit. To reduce the computation time, a scenario reduction algorithm is applied to select fewer scenarios with properties similar to the original scenarios. Finally we solve the stochastic mixed-integer program with the Progressive Hedging Algorithm (PHA), which is a scenario-based decomposition heuristic. We compare the results of the stochastic program and a deterministic optimization using expected values. The capacity expansion plan obtained with the stochastic program has higher expected social welfare than the expected value solution. The stochastic program yields a solution that hedges against uncertainty by lower generation expansion levels and fewer transmission lines to be built.