LT Plan - Stochastic Optimization
Contents
1. Stochastic Programming
Stochastic optimization is available as part of both LT Plan and MT Schedule. Firstly some background on Stochastic Programming:
"Stochastic programming is a framework for modelling optimization problems that involve uncertainty. Whereas deterministic optimization problems are formulated with known parameters, real world problems almost invariably include some unknown parameters. When the parameters are known only within certain bounds, one approach to tackling such problems is called robust optimization. Here the goal is to find a solution which is feasible for all such data and optimal in some sense. Stochastic programming models are similar in style but take advantage of the fact that probability distributions governing the data are known or can be estimated. The goal here is to find some policy that is feasible for all (or almost all) the possible data instances and maximizes the expectation of some function of the decisions and the random variables. More generally, such models are formulated, solved analytically or numerically, and analyzed in order to provide useful information to a decision-maker."''Source: http://www.stoprog.org "Stochastic Programming Community"
Stochastic Programming (SP) is not the same as solving multiple deterministic 'scenarios' and applying weights to the results. In that case you will get N sets of decisions, and it can be very difficult to reconcile those into a single decision 'now'. In SP we wish to find a single solution to key decisions e.g. the timing and size of new generation builds, that is optimal given the uncertainty in certain variables e.g. uncertainty in hydro inflows.
LT Plan formulates and solves Stochastic Integer Programming (SIP) problems. Here at least some of the decision variables are integer (e.g. the number of new generating units built in a year). The solution technique is scenario-wise decomposition. Scenario-wise decomposition is suitable when the random problem elements can take discrete scenarios e.g. sequences of hydro inflows with estimated probabilities. We then select the set of non-anticipative variables whose values must be optimized w.r.t. the uncertainty e.g. the generator build decisions.
Copies of the non-anticipative variables are introduced for each scenario. Additional constraints, known as the non-anticipativity constraints guarantee that the non-anticipative variables are identical across the different scenarios. Consider the Lagrangian dual problem obtained by relaxing the non-anticipativity constraints through the introduction of Lagrange multipliers. Note that for a given set of multipliers, the problem is separable by scenarios, thus the dual function can be evaluated in a decomposed manner. Optimization of the dual function can be performed using standard non-smooth optimization techniques. However, owing to the non-convexities, there exists a duality gap, and one needs to resort to a branch-and-bound strategy to prove optimality—see C. C. Caroe and R.Schultz. Dual decomposition in stochastic integer programming. Operations Research Letters, 24:37-45, 1999.
Mixed-integer programming (MIP) is used to solve the SIP problem. It is only in recent times that advances in modern MIP techniques has permitted the solution of SIP problems on the scale of power systems problems.
2. Stochastic LT Plan
2.1. Stochastic Integer Programming
LT Plan includes the attribute Stochastic Method which controls how stochastic elements (Variable objects) are handled in LT Plan. To enable stochastic optimization simply toggle this switch to 'scenario-wise decomposition'. You then use the Stochastic object attached to your Model to set the number of scenarios (samples) to be solved, just as you would if you were solving 'independent samples'.
At runtime the simulator proceeds by formulating the production part of the capacity expansion problem S times (where S is the number of samples). Each of these production problems will have different values for the stochastic elements. It then adds S sets of the non-anticipative variables (the expansion decisions). Finally it adds the non-anticipativity constraints, which force the non-anticipative variables to be equal across all S scenarios.
2.2. Non-anticipativity Period
In multi-annual optimization it can be viewed as overly restrictive that the non-anticipative variables match in later years, since in reality the decision maker would have time to adjust to actual outcomes. The following properties allow you to control when certain non-anticipativity constraints can be violated:
- Generator Build Non-anticipativity
- Generator Retire Non-anticipativity
- Line Build Non-anticipativity
- Line Retire Non-anticipativity
- Physical Contract Build Non-anticipativity
In all cases the simulator assumes that the non-anticipativity constraints are not required unless you deliberately define these properties i.e. if you do not define these properties on any generators/lines/physical contracts that have build/retire decisions then the stochastic optimization will produce different outcomes for each of the S samples. Thus it is often safest to define the property deliberately for all expansion candidates, for example:
| Generator | Property | Value | Unit | Date From |
|---|---|---|---|---|
| Big Unit | Max Units Built | 1 | - | |
| Big Unit | Economic Life | 25 | years | |
| Big Unit | WACC | 12 | % | |
| Big Unit | Build Cost | 1200 | $/kW/year | |
| Big Unit | Build Non-anticipativity | -1 | - | |
| Big Unit | Build Non-anticipativity | 1000 | $/MW | 1/01/2015 |
| Small Unit | Max Units Built | 1 | - | |
| Small Unit | Economic Life | 25 | years | |
| Small Unit | WACC | 12 | % | |
| Small Unit | Build Cost | 1200 | $/kW/year | |
| Small Unit | Build Non-anticipativity | 0 | - |
In the above example, the Generator "Big Unit" sets Build Non-anticipativity to -1 (which means a 'hard constraint') until 1/01/2015 when the constraint is allowed to be violated at a cost of $1000/MW. In the optimal solution then all stochastic scenarios will have the same single decision for "Big Unit" up until 1/01/2015 and beyond that the build decision for that generator may vary by scenario.
2.3. Stochastic Hydro Optimization
The following Storage property is also provided:
This differs from the other non-anticipativity properties in that it refers to a linear set of decisions in the production part of the problem; and it is also available in MT Schedule.
Setting this property on a Storage tells LT Plan that a single optimal storage trajectory must be chosen for the storage considering the uncertainty in the problem e.g. hydro inflows, but also other uncertainty as defined by the stochastic samples. This is most suitable for medium to long term storages and results is a more conservative (and realistic) operation of those storage.
2.4. Using Stochastic LT Plan
In summary then, the simulator can perform true stochastic optimization and provide extremely valuable/useful decisions as a result. Here is a check list of items you must define and options you must enable to get this function working:
- Create one or more Variable objects to generate or directly input the independent samples for your uncertain elements e.g. hydro inflows, loads, fuel prices.
- Attach a Stochastic object to your Model and set the number of samples to be evaluated.
- In LT Plan set the Stochastic Method to 'scenario-wise decomposition'.
- Identify the non-anticipative variables using the non-anticipativity properties.
The problem is then solved using MIP in a single optimization. Note that the size of the task to be optimized increases linearly with S, and so the run time is likely to increase quadratically or worse. Thus it is a good idea to limit S. For real sized systems where the time frame is 10's of years it is likely that memory requirements will be high, and it might be necessary to use the 64-bit version of the simulator in order to meet the memory requirements.