A Planner-Trader Decomposition for Multi-Market Hydro Scheduling

Peak/off-peak spreads on European electricity forward and spot markets are eroding due to the ongoing nuclear phaseout and the steady growth in photovoltaic capacity. The reduced profitability of peak/off- peak arbitrage forces hydropower producers to recover part of their original profitability on the reserve markets. We propose a bi-layer stochastic programming framework for the optimal operation of a fleet of interconnected hydropower plants that sells energy on both the spot and the reserve markets. The outer layer (the planner’s problem) optimizes end-of-day reservoir filling levels over one year, whereas the inner layer (the trader’s problem) selects optimal hourly market bids within each day. Using an information restriction whereby the planner prescribes the end-of-day reservoir targets one day in advance, we prove that the trader’s problem simplifies from an infinite-dimensional stochastic program with 25 stages to a finite two- stage stochastic program with only two scenarios. Substituting this reformulation back into the outer layer and approximating the reservoir targets by affine decision rules allows us to simplify the planner’s problem from an infinite-dimensional stochastic program with 365 stages to a two-stage stochastic program that can conveniently be solved via the sample average approximation. Numerical experiments based on a cascade in the Salzburg region of Austria demonstrate the effectiveness of the suggested framework.

Generalized Decision Rule Approximations for Stochastic Programming via Liftings

Daniel Kuhn, Wolfram Wiesemann

Stochastic programming provides a versatile framework for decision-making under uncertainty, but the resulting optimization problems can be computationally demanding. It has recently been shown that, primal and dual linear decision rule approximations can yield tractable upper and lower bounds on the optimal value of a stochastic program. Unfortunately, linear decision rules often provide crude approximations that result in loose bounds. To address this problem, we propose a lifting technique that maps a given stochastic program to an equivalent problem on a higher-dimensional probability space. We prove that solving the lifted problem in primal and dual linear decision rules provides tighter bounds than those obtained from applying linear decision rules to the original problem. We also show that there is a one-to-one correspondence between linear decision rules in the lifted problem and families of non-linear decision rules in the original problem. Finally, we identify structured liftings that give rise to highly flexible piecewise linear decision rules and assess their performance in the context of a stylized investment planning problem.

Springer Verlag2015

Scalable Stochastic Optimization: Scenario Reduction with Guarantees

Kilian Schindler

Stochastic optimization is a popular modeling paradigm for decision-making under uncertainty and has a wide spectrum of applications in management science, economics and engineering. However, the stochastic optimization models one faces in practice are intractable, and numerical solutions necessitate approximations. The mainstream approach for making a stochastic optimization model amenable to numerical solution is to discretize the probability distribution of the uncertain problem parameters. However, both the accuracy of the approximation as well as the computational burden of solving the approximate problem scale with the number of scenarios of the approximate distribution. An effective means to ease the computational burden is to use scenario reduction, which replaces an accurate initial distribution accommodating many scenarios with a simpler distribution supported on only few scenarios that is close to the initial distribution with respect to a probability metric. Using the Wasserstein distance as measure of proximity between distributions, we provide new insights into the fundamental limitations of scenario reduction, and we propose the first polynomial-time constant-factor approximations for a popular scenario reduction problem from the literature. As scenario reduction is equivalent to clustering, it suffers from two well-known shortcomings. Namely, it suffers from outlier sensitivity and may produce highly unbalanced clusters. To mitigate both shortcomings, we formulate a joint outlier detection and clustering problem, where the clusters must satisfy certain cardinality constraints. We cast this problem as a mixed-integer linear program (MILP) that admits tractable semidefinite and linear programming relaxations. We propose deterministic rounding schemes that transform the relaxed solutions to feasible solutions for the MILP. We also prove that these solutions are optimal in the MILP if a cluster separation condition holds. Finally, we develop a highly efficient scenario reduction method for a large-scale hydro scheduling problem. Specifically, we study the optimal operation of a fleet of interconnected hydropower plants that sell energy on both the spot and the reserve markets, and we propose a two-layer stochastic programming framework for its solution. The outer layer problem (the planner's problem) optimizes the end-of-day reservoir filling levels over one year, whereas the inner layer problem (the trader's problem) selects optimal hourly market bids within each day. We prove that the trader's problem admits a scenario reduction that dramatically reduces its complexity without loss of optimality, which in turn facilitates an efficient approximation of the planner's problem.

EPFL2020

Distributionally Robust Optimization with Markovian Data

Daniel Kuhn, Mengmeng Li, Tobias Sutter

We study a stochastic program where the probability distribution of the uncertain problem parameters is unknown and only indirectly observed via finitely many correlated samples generated by an unknown Markov chain with d states. We propose a data-driven distributionally robust optimization model to estimate the problem’s objective function and optimal solution. By leveraging results from large deviations theory, we derive statistical guarantees on the quality of these estimators. The underlying worst-case expectation problem is nonconvex and involves O(d^2) decision variables. Thus, it cannot be solved efficiently for large d. By exploiting the structure of this prob- lem, we devise a customized Frank-Wolfe algorithm with convex direction-finding subproblems of size O(d). We prove that this algorithm finds a stationary point efficiently under mild conditions. The efficiency of the method is predicated on a dimensionality reduction enabled by a dual reformulation. Numerical experiments indicate that our approach has better computational and statistical properties than the state-of-the-art methods.

2021

Scalable Stochastic Optimization: Scenario Reduction with Guarantees

Kilian Schindler

EPFL2020