# Dual Dynamic Programming Algorithm

`Dolphyn.add_cut`

— Method`function add_cut(EP_cur::Model, EP_next::Model, start_cap_d::Dict, cap_track_d::Dict)`

inputs:

- EP_cur - JuMP model from the current model stage $p$.
- EP_next - JuMP model from the next model stage $p+1$..
- start_cap_d – Dictionary which contains key-value pairs of available capacity investment expression names (as Symbols) as keys and their corresponding linking constraint names (as Symbols) as values.
- cap_track_d – Dictionary which contains key-value pairs of capacity addition and retirement tracking variable names (as Symbols) as keys and their corresponding linking constraint names (as Symbols) as values.

returns: JuMP expression representing a sum of Benders cuts for linking capacity investment variables to be added to the cost-to-go function.

`Dolphyn.configure_ddp_dicts`

— Method`function configure_ddp_dicts(setup::Dict, inputs::Dict)`

This function instantiates Dictionary objects containing the names of linking expressions, constraints, and variables used in multi-stage modeling.

inputs:

- setup - Dictionary object containing GenX settings and key parameters.
- inputs – Dictionary of inputs for each model period, generated by the load_inputs() method.

returns:

- start_cap_d – Dictionary which contains linking expression names as keys and linking constraint names as values, used for setting the end capacity in stage $p$ to the starting capacity in stage $p+1$.
- cap_track_d – Dictionary which contains linking variable names as keys and linking constraint names as values, used for enforcing endogenous retirements.

`Dolphyn.fix_capacity_tracking`

— Method`function fix_capacity_tracking(EP_prev::Model, EP_cur::Model, cap_track_d::Dict, cur_stage::Int)`

This function sets the right hand side values of the new and retired capacity tracking linking constraints in the current stage $p$ to the realized values of the new and retired capacity tracking linking variables from the previous stage $p-1$ as part of the forward pass. where tracking linking variables are defined variables for tracking, linking and passing realized expansion and retirement of capacities of each stage to the next stage. Tracking linking variables are each defined in endogenous_retirement_discharge, endogenous_retirement_energy, and endogenous_retirement_charge functions. Three examples are "vCAPTRACK", "vCAPTRACKCHARGE", and ""vCAPTRACKENERGY"

inputs:

- EP_prev - JuMP model from the previous model stage $p-1$.
- EP_cur - JuMP model from the current model stage $p$.
- cap_track_d – Dictionary which contains key-value pairs of capacity addition and retirement tracking variable names (as Symbols) as keys and their corresponding linking constraint names (as Symbols) as values.
- cur_period – Int representing the current model stage $p$.

returns: JuMP model with updated linking constraints.

`Dolphyn.fix_initial_investments`

— Method`function fix_initial_investments(EP_prev::Model, EP_cur::Model, start_cap_d::Dict)`

This function sets the right hand side values of the existing capacity linking constraints in the current stage $p$ to the realized values of the total available end capacity linking variable expressions from the previous stage $p-1$ as part of the forward pass.

inputs:

- EP_prev - JuMP model from the previous model stage $p-1$.
- EP_cur - JuMP model from the current model stage $p$.
- start_cap_d – Dictionary which contains key-value pairs of available capacity investment expression names (as Symbols) as keys and their corresponding linking constraint names (as Symbols) as values.

returns: JuMP model with updated linking constraints.

`Dolphyn.generate_cut_component_inv`

— Method`function generate_cut_component_inv(EP_cur::Model, EP_next::Model, expr_name::Symbol, constr_name::Symbol)`

This function generates Bender's cut expressions for linking capacity investment variable expression in the form:

\[\begin{aligned} \mu_{next}^{\top}(\hat{x}_{cur} - x_{cur}) \end{aligned}\]

where $\mu_{next}$ is a vector of dual values of the linking constraints defined by constr_name in EP_next, $\hat{x}_{cur}$ is a vector of realized values from the forward pass of the linking capacity investment variable expressions expr_name from EP_cur, and $x_{cur}$ is a vector of unrealized linking capacity investment variable expressions from EP_cur. inputs:

inputs:

- EP_cur - JuMP model from the current model stage $p$, solved in the forward pass.
- EP_next - JuMP model from the next model stage $p+1$, solved in the forward pass.
- expr_name – Symbol representing the name of a JuMP expression array which contains linking capacity investment variables.
- constr_name – Symbol representing the name of the array of linking JuMP constraints which contain the linking capacity investment variables.

returns: JuMP expression representing a sum of Benders cuts for linking capacity investment variables to be added to the cost-to-go function.

`Dolphyn.generate_cut_component_track`

— Method`function generate_cut_component_inv(EP_cur::Model, EP_next::Model, expr_name::Symbol, constr_name::Symbol)`

This function generates Bender's cut expressions for total new or retired capacity tracking linking variables in the form:

\[\begin{aligned} \mu_{next}^{\top}(\hat{x}_{cur} - x_{cur}) \end{aligned}\]

where $\mu_{next}$ is a vector of dual values of the linking constraints defined by constr_name in EP_next, $\hat{x}_{cur}$ is a vector of realized values from the forward pass of the new or retired capacity tracking linking variables var_name from EP_cur, and $x_{cur}$ is a vector of unrealized new or retired capacity tracking linking variables from EP_cur.

inputs:

- EP_cur - JuMP model from the current model stage $p$.
- EP_next - JuMP model from the next model stage $p+1$.
- var_name – Symbol representing the name of a JuMP variable array which contains total new or retired capacity tracking linking variables.
- constr_name – Symbol representing the name of the array of linking JuMP constraints which contain total new or retired capacity tracking linking variables.

returns: JuMP expression representing a sum of Benders cuts for linking capacity investment variables to be added to the cost-to-go function.

`Dolphyn.initialize_cost_to_go`

— Method`function initialize_cost_to_go(settings_d::Dict, EP::Model)`

This function scales the model objective function so that costs are consistent with multi-stage modeling and introduces a cost-to-go function variable to the objective function.

The updated objective function $OBJ^{*}$ returned by this method takes the form:

\[\begin{aligned} OBJ^{*} = DF * OPEXMULT * OBJ + \alpha \end{aligned}\]

where $OBJ$ is the original objective function. $OBJ$ is scaled by two terms. The first is a discount factor (applied only in the non-myopic case), which discounts costs associated with the model stage $p$ to year-0 dollars:

\[\begin{aligned} DF = \frac{1}{(1+WACC)^{L*(p-1)}} \end{aligned}\]

where $WACC$ is the weighted average cost of capital, and $L$ is the length of each stage in years (both set in multi_stage_settings.yml)

The second term is a discounted sum of annual operational expenses incurred each year of a multi-year model stage:

\[\begin{aligned} & OPEXMULT = \sum^{L}_{l=1}\frac{1}{(1+WACC)^{l-1}} \end{aligned}\]

Note that although the objective function contains investment costs, which occur only once and thus do not need to be scaled by OPEXMULT, these costs are multiplied by a factor of $\frac{1}{WACC}$ before being added to the objective function in investment_discharge_multi_stage(), investment_charge_multi_stage(), investment_energy_multi_stage(), and transmission_multi_stage(). Thus, this step scales these costs back to their correct value.

The cost-to-go function $\alpha$ represents an approximation of future costs given the investment and retirement decisions in the current stage. It is constructed through the addition of cuts to the cost-to-go function $\alpha$ during the backwards pass.

inputs:

- settings_d - Dictionary containing settings dictionary configured in the multi-stage settings file multi_stage_settings.yml.
- EP – JuMP model.

returns: JuMP model with updated objective function.

`Dolphyn.run_ddp`

— Method`function run_ddp(models_d::Dict, setup::Dict, inputs_d::Dict)`

This function run the dual dynamic programming (DDP) algorithm, as described in Pereira and Pinto (1991), and more recently, Lara et al. (2018). Note that if the algorithm does not converge within 10,000 (currently hardcoded) iterations, this function will return models with sub-optimal solutions. However, results will still be printed as if the model is finished solving. This sub-optimal termination is noted in the output with the 'Exiting Without Covergence!' message.

inputs:

- models_d – Dictionary which contains a JuMP model for each model period.
- setup - Dictionary object containing GenX settings and key parameters.
- inputs_d – Dictionary of inputs for each model stage, generated by the load_inputs() method.

returns:

- models_d – Dictionary which contains a JuMP model for each model stage, modified by this method.
- stats_d – Dictionary which contains the run time, upper bound, and lower bound of each DDP iteration.
- inputs_d – Dictionary of inputs for each model stage, generated by the load_inputs() method, modified by this method.

`Dolphyn.write_multi_stage_outputs`

— Method`function write_multi_stage_outputs(stats_d::Dict, outpath::String, settings_d::Dict)`

This function calls various methods which write multi-stage modeling outputs as .csv files.

inputs:

- stats_d – Dictionary which contains the run time, upper bound, and lower bound of each DDP iteration.
- outpath – String which represents the path to the Results directory.
- settings_d - Dictionary containing settings configured in the GenX settings genx_settings.yml file as well as the multi-stage settings file multi_stage_settings.yml.

## Suggested Reading

The solution strategy implemented for solving the multi-stage investment planning model follows the decomposition algorithm described in Lara et al, Deterministic electric power infrastructure planning: Mixed-integer programming model and nested decomposition algorithm, European Journal of Operations Research, 271(3), 1037-1054, 2018. The decomposition algorithm adapts previous nested Benders methods by handling integer and continuous state variables, although at the expense of losing its finite convergence property due to potential duality gap.