We consider multistage stochastic convex programs with a random number of stages. We explain how to write Dynamic Programming equations for these problems and how to extend the Stochastic Dual Dynamic Programming (SDDP) method to solve these equations. We then introduce and study two extensions of SDDP method: an inexact variant that solves some or all subproblems approximately and a variant, called StoDCuP (Stochastic Dynamic Cutting Plane), which linearizes not only all Bellman functions but also some or all nonlinear cost and constraint functions.

O trabalho faz parte do projeto de aperfeiçoamento dos modelos de planejamento da expansão da EPE. Será detalhado o modelo estocástico de otimização do despacho hidrotérmico, via algoritmo PDDE, enfatizando inovações, em relação às implementações mais conhecidas no setor elétrico: representação do modelo hidrológico por cadeias de Markov e resolução do “efeito fim do mundo” por uma técnica de recursão infinita.

Enquanto a primeira proposta objetiva simplificar o processo de estimação do modelo estatístico de vazões, a segunda visa reduzir o tamanho e complexidade do problema de otimização.

We propose a new algorithm for solving multistage stochastic mixed integer linear programming (MILP) problems with complete continuous recourse based on a generalized class of nonlinear Lipschitz cuts. In a similar way to cutting plane methods, we construct augmented Lagrangian cuts and reverse norm cuts to build lower approximations for non-convex cost-to-go functions, and we resort to the tightness property of those cuts to prove convergence to an optimal (or epsilon optimal) policy. The family of Lipschitz cuts we used in our experiments is MILP representable so we keep in the mixed integer framework along all the optimization process. We illustrate the application of this algorithm on two simple case studies, comparing our approach with the convex relaxation and the discretized approximation of the problems, for which we can apply SDDP and SDDiP, respectively.

In this talk, an alternative methodology for devising revenue-maximizing strategic bids under uncertainty in the competitors’ strategic behavior is presented. We focus on markets endowed with a sealed-bid uniform-price auction with multiple divisible products (e.g., day-ahead electricity markets). On recognizing that the bids of competitors may deviate from equilibrium and are of difficult statistical characterization, a two-stage robust optimization model with equilibrium constraints is designed aiming to devise risk-averse strategic bids. The proposed model is a trilevel optimization problem that can be recast as a particular instance of a bilevel program with equilibrium constraints. Reformulation procedures to construct a single-level equivalent formulation suitable for column-and-constraint generation (CCG) algorithm are presented. Firstly, the complementarity conditions used to ensure auction equilibrium constraints are expressed through binary relations between dual and slack variables of the third-level problem. Then, a single-level equivalent formulation with an exponential number of constraints is devised. Finally, an efficient solution methodology is designed by applying a tailored CCG algorithm on the single-level equivalent exponential formulation. The algorithm explores the binary nature of the complementarity conditions and, to avoid the full enumeration of the exponential set of constraints, identifies a reduced set of binary relations which is sufficient to represent the complementarity conditions that ensure the auction equilibrium constraints at the optimal bidding strategy. To conclude, numerical experiments are presented to illustrate the effectiveness and intuition of the solution proposal and the benefits of including robustness into the strategic bidding process in a day-ahead electricity market application. Results show that even for the case in which an imprecision of 1% is observed on the rivals’ bids in the equilibrium point, the robust solution provides a significant risk reduction (of 79.9%) in out-of-sample tests. They also indicate that the best strategy against high levels of uncertainty on competitors’ bid approaches to a price-taker offer, i.e., bid maximum capacity at marginal cost.

Hydrothermal operation is a well-known large-scale, real-life, application of stochastic multistage optimization techniques. Algorithms such as hybrid Dynamic Programming and Stochastic Dual Dynamic Programming (SDDP/DP) have been successfully applied to these problems, where SDDP with weekly stages is used to manage inflow uncertainty, usually represented as an autoregressive stochastic model. In systems with a high penetration of renewables, there is another level of uncertainty at the intra-week scale: the variability of energy production from wind and solar sources, combined with net load variability driven by factors such as temperature and cloud cover (e.g. due to air conditioning and rooftop solar).

The objective function of this week-ahead scheduling problem (WASP) is to minimize the expected value of the sum of operation costs along the hours (or 15-minute intervals) along the week plus the expected future operation cost at the end of the week, represented by the well-known future cost function produced by the SDDP/DP algorithms.

In the authors’ experience, the main challenges in solving WASP are: (i) the linear stochastic models used in SDDP/DP are not adequate to represent the complex, nonlinear relationship between wind, solar and net load; (ii) the effect of diverse forecasting techniques for these value has to be considered in the optimization process; (iii) it is also necessary to represent time-coupling constraints such as ramps on hydro outflow and forebay variation, minimum uptime and downtime for the committed thermal plants.

This paper presents a hybrid probabilistic solution approach to WASP based on the following methodologies and assumptions: (i) Integrated scenarios of hourly renewable production and net loads, plus weekly/daily inflows to the hydro plants; (ii) A probabilistic forecasting model assigns weights to these scenarios, reflecting the fact that forecasting accuracy varies with time; (iii) A spatial/severity clustering algorithm to divide the scenarios into subsets; and (iv) A multivariate set of affine functions, related to the clusters identified in step (iii), is used as part of a multistage MIP optimization problem to determine the optimal scheduling under uncertainty for the weighted scenarios produced in steps (i) and (ii).

The above approach will be illustrated with the scheduling of the detailed generation-transmission system of Chile, which has a complex mix of hydro, wind, solar and fossil fuel plants such as combined cycle gas and coal.

The current state-of-the-art method used for medium- and long-term planning studies of hydrothermal power system operation is the stochastic dual dynamic programming (SDDP) algorithm. The computational savings provided by this method notwithstanding, it still relies on major system simplifications to achieve acceptable performances in practical applications. In contrast with its actual implementation, simplifications in the planning stage may induce time-inconsistent policies, and consequently, a suboptimality gap. In this paper, we extend the concept of time inconsistency to measure the effects of modeling simplifications in the SDDP framework for hydrothermal operation planning. Case studies involving simplifications in transmission lines modeling and in security criteria indicate that these source of time inconsistency may result in unexpected reservoir depletion and spikes in energy market spot prices.

TBA

Muitas são as simplificações necessárias para o desenvolvimento e utilização dos modelos de despacho do SIN. Se por um lado tais simplificações viabilizam a utilização sistemática dos modelos, por outro lado elas diminuem a aderência dos resultados computacionais com a realidade da operação do sistema. Nesse contexto, esse trabalho tem por objetivo apresentar os níveis de aproximações implícitos nos modelos de otimização estocástica com amostragem e algumas de suas implicações nos resultados da simulação da operação. Além disso, também será apresentada uma breve discussão sobre os desafios do acoplamento entre modelos de despacho com distintos níveis de aproximações e algoritmos de solução, conforme utilizado oficialmente no Brasil.

Power system planning and operation is a very complex task, specially in hydrothermal systems. This talk briefly describes the main stochastic programming algorithms that have been applied and continuously improved for over twenty years for the planning, operation and price setting of the large-scale Brazilian system. It focuses on the main challenges and issues imposed by the official application of optimization tools in a multi-agent system, such as: the trade-off between CPU time, system representation and quality of the policy; reproducibility and stability of the results; multi-criteria analysis for parameter definition, taking into account system security and impact on prices. Several analyses are conducted under working groups and task forces with the participation of several institutions and power utilities, leading to the development of robust, reliable and efficient tools for the planning and operation of power systems. Finally, It also presents the latest developments for the establishment of hourly prices in Brazil and to address the complicating aspects related to the uncertainty and high variability of intermittent generation as wind and solar plants.

We present a distributionally robust optimization (DRO) approach for the transmission expansion planning problem, considering both long- and short-term uncertainties on the system demand and renewable generation. On the longterm level, as it is customary in industry applications, the deep uncertainties arising from social and economic transformations, political and environmental issues, and technology disruptions are addressed by long-term scenarios devised by experts. The system planner is then allowed to consider exogenous long-term scenarios containing partial information about the random parameters, namely, the average and the support set. For each constructed long-term scenario, a conditional ambiguity set is used to model the incomplete knowledge about the probability distribution of the uncertain parameters in the short-term. Consequently, the mathematical problem is formulated as a DRO model with multiple conditional ambiguity sets. The resulting infinite-dimensional problem is recast as an exact, although very large, finite-deterministic mixedinteger linear programming problem. To circumvent scalability issues, we propose a new enhanced-column-and-constraintgeneration (ECCG) decomposition approach with an additional Dantzig–Wolfe procedure. In comparison to existing methods, ECCG leads to a better representation of the recourse function and, consequently, tighter bounds. Numerical experiments based on the benchmark IEEE 118-bus system are reported to corroborate the effectiveness of the method.