Algorithms for Stochastic Mixed-integer Nonlinear Programming and Long Term Optimization of Electric Power Systems

This thesis addresses two challenging problems. The first part is focused on developing algorithms and software for two-stage stochastic mixed-integer nonlinear programming problems (SMINLPs). The second part is on the longterm

planning of power systems. Stochastic programming, also known as stochastic optimization, is a mathematical

framework to model decision-making under uncertainty that has been widely applied in process systems engineering (PSE). Two-stage stochastic mixed integer programming (SMIPs) is a special case of stochastic programming that

considers first and second stage decisions made sequentially with both discrete and continuous variables. Although there have been algorithmic advances in

linear SMIPs, the decomposition algorithms to address the nonlinear counterpart, stochastic mixed-integer nonlinear programs (SMINLPs), are few. In Part I of this thesis, we propose four decomposition algorithms for different classes

of SMINLPs. For SMINLPs with convex nonlinear constraints, mixed-binary first and second variables, and discrete probability distributions, we propose an improved L-shaped algorithm that combines strengthened Benders cuts and Lagrangean cuts. This algorithm has no guarantee of global optimality. To close the optimality gap, we propose a generalized Benders decomposition-based branch-and-bound algorithm where the stage two problems are convexified sequentially by performing basic steps. For SMINLPs with nonconvex constraints, mixed-binary first and second variables, and discrete probability distributions,

we propose a generalized Benders decomposition-based branch-and-cut algorithm where we combine the Benders cuts derived from convexification of the stage two problems and the Lagrangean cuts. A spatial branch-and-cut algorithm is performed to guarantee convergence to global optimality. Last but not least, a sample-average approximation-based outer approximation algorithm is proposed for nonconvex SMINLPs with continuous probability distributions. This algorithm does internal sampling within an outer approximation framework using confidence interval estimates. Part II addresses generation expansion planning of power systems under high penetration of renewables. We propose a mixed-integer linear programming (MILP) model that incorporates both the investment decisions on the generating units, storage units, and transmission lines, and short-term unit commitment decisions to capture the variations of the renewables. To make the large-scale MILP

model tractable, we propose several spatial and temporal aggregation schemes and adapt the Benders decomposition algorithm and the nested Benders decomposition algorithm to solve the problem efficiently. We also investigate several

different algorithms to select the representative days. Case studies of the ERCOT region are provided to demonstrate the capabilities of our approaches.