River optimization: short-term hydropower bidding under uncertainty.

Summary The hydro-offer problem consists of computing optimal bidding conditions to maximize the expected profit of a hydro producer participating in an electricity market. It combines the decision making process of the trader and the hydro dispatcher into a single stochastic optimization problem. It is a sequential decision making problem, and can be formulated as a multi-stage 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 similarly to Stochastic Dual Dynamic Programming (SDDP), but instead of using hyperplanes, it uses step functions to create an outer approximation of the value function. MIDAS converges "almost surely" to (T+1)ε optimal solution when continuous state variables, and to the exact optimal solution when integer state variables.We use MIDAS to solve three types of hydro-bidding problems that are nonconvex. The first hydro-bidding model we solve for integer state variables because the outputs are discrete. In this model, we show that MIDAS constructions offer that are better than SDDP. The next hydro-bidding model uses autoregressive price processes instead of a Markov chain. The last hydro-bidding model incorporates headwater effects, where the power generation function depends on the reservoir storage level and the turbine water flow rate. In all these models, we demonstrate the convergence of MIDAS in finite iterations.The convergence time of MIDAS is higher than SDDP because subproblems is the mixed-integer programs (MIP). For hydraulic auction models with continuous state variables, its computation time depends on the value of the δ. If the δ is large, then it reduces the convergence computation time but it also increases the 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 MIP subproblems in MIDAS using smaller MIPs, rather than as a single large MIP. This heuristic improves the solution time by up to 60%. By applying both heuristics, we were able to use MIDAS to solve a hydro-bidding problem with 4 reservoirs, 4 stations and integer state variables.