We provide a comprehensive overview of mixed integer programming formulations for the unit commitment problem (UC). UC formulations have been an especially active area of research over the past twelve years, due to their practical importance in power grid operations, and this paper serves as a capstone for this line of work. We additionally provide publicly available reference implementations of all formulations examined. We computationally test existing and novel UC formulations on a suite of instances drawn from both academic and real-world data sources. Driven by our computational experience from this and previous work, we contribute some additional formulations for both production upper bound and piecewise linear produc- tion costs. By composing new UC formulations using existing components found in the literature and new components introduced in this paper, we demonstrate that performance can be significantly improved – and in the process, we identify a new state-of-the-art UC formulation.
In this work, we show that a strong upper bound on the objective of the alternating current optimal power flow (ACOPF) problem can significantly improve the effectiveness of optimization-based bounds tightening (OBBT) on a number of relaxations. We additionally compare the performance of relaxations of the ACOPF problem, including the rectangular form without reference bus constraints, the rectangular form with reference bus constraints, and the polar form. We find that relaxations of the rectangular form significantly strengthen existing relaxations if reference bus constraints are included. Overall, relaxations of the polar form perform the best. However, neither the rectangular nor the polar form dominates the other. In conclusion, with these strategies, we are able to reduce the optimality gap to less than 0.1% on all but 5 NESTA test cases with up to 300 buses by performing OBBT alone.
We present a novel formulation for startup cost computation in the unit commitment problem (UC). Both the proposed formulation and existing formulations in the literature are placed in a formal, theoretical dominance hierarchy based on their respective linear programming relaxations. The proposed formulation is tested empirically against existing formulations on large-scale unit commitment instances drawn from real-world data. While requiring more variables than the current state-of-the-art formulation, our proposed formulation requires fewer constraints, and is empirically demonstrated to be as tight as a perfect formulation for startup costs. This tightening reduces the computational burden in comparison to existing formulations, especially for UC instances with large variability in net-load due to renewables production.
Stochastic optimization deals with making highly reliable decisions under uncertainty. Chance constraints are a crucial tool of stochastic optimization to develop mathematical optimization models; they form the backbone of many important national security data science applications. These include critical infrastructure resiliency, cyber security, power system operations, and disaster relief management. However, existing algorithms to solve chance-constrained optimization models are severely limited by problem size and structure. In this investigative study, we (i) develop new algorithms to approximate chance-constrained optimization models, (ii) demonstrate the application of chance-constraints to a national security problem, and (iii) investigate related stochastic optimization problems. We believe our work will pave way for new research is stochastic optimization as well as secure national infrastructures against unforeseen attacks.
We present novel stochastic optimization models to improve power systems resilience to extreme weather events. We consider proactive redispatch, transmission line hardening, and transmission line capacity increases as alternatives for mitigating expected load shed due to extreme weather. Our model is based on linearized or "DC" optimal power flow, similar to models in widespread use by independent system operators (ISOs) and regional transmission operators (RTOs). Our computational experiments indicate that proactive redispatch alone can reduce the expected load shed by as much as 25% relative to standard economic dispatch. This resiliency enhancement strategy requires no capital investments and is implementable by ISOs and RTOs solely through operational adjustments. We additionally demonstrate that transmission line hardening and increases in transmission capacity can, in limited quantities, be effective strategies to further enhance power grid resiliency, although at significant capital investment cost. We perform a cross validation analysis to demonstrate the robustness of proposed recommendations. Our proposed model can be augmented to incorporate a variety of other operational and investment resilience strategies, or combination of such strategies.
Stochastic versions of the unit commitment problem have been advocated for addressing the uncertainty presented by high levels of wind power penetration. However, little work has been done to study trade-offs between computational complexity and the quality of solutions obtained as the number of probabilistic scenarios is varied. Here, we describe extensive experiments using real publicly available wind power data from the Bonneville Power Administration. Solution quality is measured by re-enacting day-ahead reliability unit commitment (which selects the thermal units that will be used each hour of the next day) and real-time economic dispatch (which determines generation levels) for an enhanced WECC-240 test system in the context of a production cost model simulator; outputs from the simulation, including cost, reliability, and computational performance metrics, are then analyzed. Unsurprisingly, we find that both solution quality and computational difficulty increase with the number of probabilistic scenarios considered. However, we find unexpected transitions in computational difficulty at a specific threshold in the number of scenarios, and report on key trends in solution performance characteristics. Our findings are novel in that we examine these tradeoffs using real-world wind power data in the context of an out-of-sample production cost model simulation, and are relevant for both practitioners interested in deploying and researchers interested in developing scalable solvers for stochastic unit commitment.
We present sufficient conditions under which thermal generators can be aggregated in mixed-integer linear programming (MILP) formulations of the unit commitment (UC) problem, while maintaining feasibility and optimality for the original disaggregated problem. Aggregating thermal generators with identical characteristics (e.g., minimum/maximum power output, minimum up/down time, and cost curves) into a single unit reduces redundancy in the search space induced by both exact symmetry (permutations of generator schedules) and certain classes of mutually nondominated solutions. We study the impact of aggregation on two large-scale UC instances: one from the academic literature and the other based on real-world operator data. Our computational tests demonstrate that, when present, identical generators can negatively affect the performance of modern MILP solvers on UC formulations. Furthermore, we show that our reformation of the UC MILP through aggregation is an effective method for mitigating this source of computational difficulty.
Electricity markets rely on the rapid solution of the optimal power flow (OPF) problem to determine generator power levels and set nodal prices. Traditionally, the OPF problem has been formulated using linearized, approximate models, ignoring nonlinear alternating current (AC) physics. These approaches do not guarantee global optimality or even feasibility in the real ACOPF problem. We introduce an outer-approximation approach to solve the ACOPF problem to global optimality based on alternating solution of upper- and lower-bounding problems. The lower-bounding problem is a piecewise relaxation based on strong second-order cone relaxations of the ACOPF, and these piecewise relaxations are selectively refined at each major iteration through increased variable domain partitioning. Our approach is able to efficiently solve all but one of the test cases considered to an optimality gap below 0.1%. Furthermore, this approach opens the door for global solution of MINLP problems with AC power flow equations.
Increasing penetration levels of renewables have transformed how power systems are operated. High levels of uncertainty in production make it increasingly difficulty to guarantee operational feasibility; instead, constraints may only be satisfied with high probability. We present a chance-constrained economic dispatch model that efficiently integrates energy storage and high renewable penetration to satisfy renewable portfolio requirements. Specifically, we require that wind energy contribute at least a prespecified proportion of the total demand and that the scheduled wind energy is deliverable with high probability. We develop an approximate partial sample average approximation (PSAA) framework to enable efficient solution of large-scale chance-constrained economic dispatch problems. Computational experiments on the IEEE-24 bus system show that the proposed PSAA approach is more accurate, closer to the prescribed satisfaction tolerance, and approximately 100 times faster than standard sample average approximation. Finally, the improved efficiency of our PSAA approach enables solution of a larger WECC-240 test system in minutes.
We describe pyomo.dae, an open source Python-based modeling framework that enables high-level abstract specification of optimization problems with differential and algebraic equations. The pyomo.dae framework is integrated with the Pyomo open source algebraic modeling language, and is available at http://www.pyomo.org. One key feature of pyomo.dae is that it does not restrict users to standard, predefined forms of differential equations, providing a high degree of modeling flexibility and the ability to express constraints that cannot be easily specified in other modeling frameworks. Other key features of pyomo.dae are the ability to specify optimization problems with high-order differential equations and partial differential equations, defined on restricted domain types, and the ability to automatically transform high-level abstract models into finite-dimensional algebraic problems that can be solved with off-the-shelf solvers. Moreover, pyomo.dae users can leverage existing capabilities of Pyomo to embed differential equation models within stochastic and integer programming models and mathematical programs with equilibrium constraint formulations. Collectively, these features enable the exploration of new modeling concepts, discretization schemes, and the benchmarking of state-of-the-art optimization solvers.