The Mixed Integer Dynamic Approximation Scheme

Get Complete Project Material File(s) Now! »

Solving hydro-bidding problems with integer state variables

In Chapter 2, we formulated the hydro-bidding problem, and applied the stochastic dual dynamic programming (SDDP) method to solve it. However, SDDP was unable to guarantee convergence if the value function is not convex (if minimizing) or not concave (if maximizing). Our motivation to solve hydro-bidding problems with non-concave value functions has led us to develop the mixed-integer dynamic approximation scheme (MIDAS). MIDAS uses step functions to approximate the value function. In Chapter 4, we presented a general MIDAS algorithm and proved its almost sure convergence with continuous and integer state variables.
In this chapter, we apply the MIDAS algorithm in order to solve a hydro-bidding model with integer state variables. The model developed in this chapter is based on HERBS (see Chapter 3 for description). It has discrete quantities where each station can choose from a predefined set of feasible power dispatches and equivalent water discharges.
Incorporating discrete production quantities makes our hydro-bidding model a Stochastic Mixed Integer Program (SMIP), which means that the state variable (i.e. reservoir storage) is integer. We solve this model using MIDAS and study its performance with respect to the quality of the computed policy and the approximation of the value function. We compare MIDAS with SDDP and illustrate that MIDAS produces better policies than SDDP due to its more accurate representation of the value function. However, solving these models, especially for large data sets, comes at computational cost, as for large problems MIDAS takes a long time and large number of steps to converge. The decrease in computational efficiency is due to the MIP representation of the sub-problems, which introduces several binary variables whenever a new step function is added.

Structure of the value function

The value function Vt+1,j(xt+1,j) in Model (5.1.1) has a unique structure. As illustrated in Figure 5.1, the structure has distinct plateaus or ’steps’, where the value function remains relatively the same for a range of state values, and then suddenly jumps to a higher value. This step-like structure has been observed by [68] for stochastic programs with integer variables in the recourse functions.

Structure of the value function

The presence of binary variables zj,s,l in the hydro-bidding model is the main reason why the value function exhibits the aforementioned structure. In the hydro-bidding model, each offer tranche ot,j defines a block dispatch that equals the total power generated across the hydro scheme. As a result of this block dispatch rule, there can be many power generation combinations across the hydro scheme which result in the same ot,j . For example, consider the power generation combination for a hydro scheme consisting of 2 reservoirs and 2 stations in cascade, described in Table 5.2. Power generation combinations of (55, 65) and (65, 55) produce a block dispatch quantity of 120 MWh. It is also a similar case for other power generation combinations.

Structure of the value function

READ FACTORS AFFECTING GROWTH, PHYSIOLOGY AND CROP WATER USE

As each generation quantity ηt,s,l corresponds to a respective water discharge θt,s,l, it couples xt+1 to ot,j in a similar manner. Table 5.3 lists the offer ot,j for each xt+1 level for a 2 reservoir hydro-scheme. Each reservoir has a net capacity of 100 cubic meters of water, and their stations have the same vector [ηt,s,l]l∈Lt,s of power generation described by Table 5.2. For various combinations of storage levels between the upstream reservoir xt+1,j,1 and downstream reservoir xt+1,j,2 the offer quantity ot,j remains constant. For instance, when xt+1,j,1 ≥ 70 the offer is 140 for all storage levels
in the downstream reservoir. This is due to the maximum water discharge capacity of the upstream station being 70. Therefore, when xt+1,j,1 ≥ 70 it discharges up to 70 cubic meters of water through the station in order to produce 70 MWh of power.
This same volume of water is also passed through the downstream station in order to produce an equivalent amount of power, thus, resulting in ot,j = 140. Table 5.3 also highlights similar instances of different, but constant, ot,j indicated by the different values. If the terminal value function VT,j(xT,j) exhibits such structure then, through recursion, this property is transferred to value functions in earlier stages, which results in the overall model inheriting this property.

1 Introduction
1.1 Electricity markets in New Zealand and France
1.2 The hydro-bidding problem
1.3 Our Contributions
1.4 Thesis structure
2 Analysis of the hydro-bidding problem
2.1 Modeling the hydro-bidding problem
2.1.1 Hydro-bidding Model Formulation
2.2 Methods of solving the hydro-bidding problem
2.2.1 Stochastic Dynamic Programming based hydro-bidding model .
2.2.2 Stochastic MIP based hydro-bidding model
2.2.3 SDDP based hydro-bidding model
2.3 Comparing hydro-bidding models
2.4 Summary
3 Hydro-bidding in the balancing market
3.1 Balancing Market Description .
3.2 Hydro-bidding in a balancing market
3.3 HERBS model formulation
3.4 Computing balancing bids using HERBS .
3.5 Limitations of HERBS
3.6 Summary .
4 The Mixed Integer Dynamic Approximation Scheme
4.1 Solving a static problem using MIDAS
4.2 Multistage optimization problem
4.3 Multistage stochastic optimization problems
4.3.1 Full-tree MIDAS algorithm
4.3.2 Sampled MIDAS algorithm
4.4 Integer State Variables
4.5 A MIP representation of QH(x)
4.6 Summary .
5 Solving hydro-bidding problems with integer state variables
5.1 The SMIP hydro-bidding model formulation
5.2 Structure of the value function
5.3 Approximating the value function
5.4 MIDAS algorithm description for hydro-bidding
5.5 Comparison of MIDAS and SDDP
5.6 Summary
6 Solving hydro-bidding problems with continuous state variables
6.1 Modelling Price Uncertainty
6.1.1 MIDAS-based approac
6.2 Modelling headwater effects
6.3 Summary
7 Improving the computation of MIDAS
7.1 Step function selection scheme
7.1.1 Analyzing computational performance of step function selection
7.2 MIP sub-problem solver
7.2.1 Analyzing computational performance of the heuristic
7.3 Solving a 4 reservoir hydro-scheme with MIDAS
7.4 Summary
8 Concluding remarks
8.1 Main results
8.2 Contributions
8.3 Future research directions
A.1 Modelling price uncertainty
A.2 Modelling headwater effects
A.2.1 Modeling unit committment
References