River Optimization: Short-term Hydro-bidding Under Uncertainty

Abstract

The hydro-bidding problem is about computing optimal offer policies in order to maximize the expected profit of a hydroelectric producer participating in an electricity market. It combines the decision making process of both the trader and the hydro-dispatcher into one stochastic optimization problem. It is a sequential decision making problem, and can be formulated as a multistage stochastic program. These models can be difficult to solve when the value function is not concave. In this thesis, we study some of the limitations of the hydro-bidding problem, and propose a new stochastic optimization method called the Mixed-Integer Dynamic Approximation Scheme (MIDAS). MIDAS solves nonconvex, stochastic programs with monotonic value functions. It works in similar fashion to the Stochastic Dual Dynamic Programming (SDDP), but instead of using cutting planes, it uses step functions to create an outer approximation of the value function. We show that MIDAS will converge almost surely to 2 optimal first stage decisions. We use MIDAS to solve three types of nonconvex hydro-bidding problems. The first hydro-bidding model we solve has integer state variables due to discrete production states. In this model we demonstrate that MIDAS constructs offer policies which are better than SDDP. The next hydro-bidding model has a mean reverting autoregressive price processs instead of a Markov chain. The last hydro-bidding incorporates headwater effects, where the power generation function is dependent on both the reservoir storage level and the turbine waterflow. In all of these models, we demonstrate convergence of MIDAS in finite iterations. MIDAS takes significantly longer to converge than SDDP due to its mixed-integer program (MIP) subproblems. For hydro-bidding models with continuous state variables, its computation time depends on the value of . A larger reduces the computation time for convergence but also increases optimality error . In order to speed up MIDAS, we introduced two heuristics. The first heuristic is a step function selection heuristic, which is similar to the cut selection scheme in SDDP. This heuristic improves the solution time by up to 64%. The second heuristic iteratively solves the MIP sub-problems in MIDAS using smaller MIPs, rather than as one large MIP. This heuristic improves the solution time up to 60%. Applying both of the heuristics, we were able to use MIDAS to solve a hydro-bidding problem, consisting of a 4 reservoir, 4 station hydro scheme with integer state variables.