API Reference

SDDPModel(;kwargs...) do ...

end

Description

This function constructs an SDDPModel. SDDPModel takes the following keyword arguments. Some are required, and some are optional.

Required Keyword arguments

• stages::Int

The number of stages in the problem. A stage is defined as each step in time at which a decion can be made. Defaults to 1.

• objective_bound

A valid bound on the initial value/cost to go. i.e. for maximisation this may be some large positive number, for minimisation this may be some large negative number. Users can pass either a single value (which bounds the cost-to-go in all stages), or a vector of values (one for each stage), or a vector (one element for each stage) of vectors of values (one value for each markov state in the stage).

• solver::MathProgBase.AbstractMathProgSolver

MathProgBase compliant solver that returns duals from a linear program. If this isn't specified then you must use JuMP.setsolver(sp, solver) in the stage definition.

Optional Keyword arguments

• sense

Must be either :Max or :Min. Defaults to :Min.

• cut_oracle::SDDP.AbstractCutOracle

The cut oracle is responsible for collecting and storing the cuts that define a value function. The cut oracle may decide that only a subset of the total discovered cuts are relevant, which improves solution speed by reducing the size of the subproblems that need solving. Currently must be one of * DefaultCutOracle() (see DefaultCutOracle for explanation) * LevelOneCutOracle()(see LevelOneCutOracle for explanation)

• risk_measure

If a single risk measure is given (i.e. risk_measure = Expectation()), then this measure will be applied to every stage in the problem. Another option is to provide a vector of risk measures. There must be one element for every stage. For example:

risk_measure = [ NestedAVaR(lambda=0.5, beta=0.25), Expectation() ]

will apply the i'th element of risk_measure to every Markov state in the i'th stage. The last option is to provide a vector (one element for each stage) of vectors of risk measures (one for each Markov state in the stage). For example:

risk_measure = [
# Stage 1 Markov 1 # Stage 1 Markov 2 #
    [ Expectation(), Expectation() ],
    # ------- Stage 2 Markov 1 ------- ## ------- Stage 2 Markov 2 ------- #
    [ NestedAVaR(lambda=0.5, beta=0.25), NestedAVaR(lambda=0.25, beta=0.3) ]
    ]

Note that even though the last stage does not have a future cost function associated with it (as it has no children), we still have to specify a risk measure. This is necessary to simplify the implementation of the algorithm.

For more help see NestedAVaR or Expectation.

• markov_transition

Define the transition probabilties of the stage graph. If a single array is given, it is assumed that there is an equal number of Markov states in each stage and the transition probabilities are stage invariant. Row indices represent the Markov state in the previous stage. Column indices represent the Markov state in the current stage. Therefore:

markov_transition = [0.1 0.9; 0.8 0.2]

is the transition matrix when there is 10% chance of transitioning from Markov state 1 to Markov state 1, a 90% chance of transitioning from Markov state 1 to Markov state 2, an 80% chance of transitioning from Markov state 2 to Markov state 1, and a 20% chance of transitioning from Markov state 2 to Markov state 2.

Returns

• m: the SDDPModel

@state(sp, stateleaving, stateentering)

Description

Define a new state variable in the subproblem sp.

Arguments

• sp the subproblem

• stateleaving any valid JuMP @variable syntax to define the value of the state variable at the end of the stage

• stateentering any valid JuMP @variable syntax to define the value of the state variable at the beginning of the stage

Examples

• @state(sp, 0 <= x[i=1:3] <= 1, x0==rand(3)[i] )

• @state(sp, y <= 1, y0==0.5 )

• @state(sp, z , z0==0.5 )

@states(sp, begin
    stateleaving1, stateentering1
    stateleaving2, stateentering2
end)

Description

Define a new state variables in the subproblem sp.

Arguments

• sp the subproblem

• stateleaving any valid JuMP @variable syntax to define the value of the state variable at the end of the stage

• stateentering any valid JuMP @variable syntax to define the value of the state variable at the beginning of the stage

Usage

@states(sp, begin
    0 <= x[i=1:3] <= 1, x0==rand(3)[i]
         y        <= 1, y0==0.5
         z            , z0==0.5
 end)

@rhsnoise(sp, rhs, constraint)

Description

Add a constraint with a noise in the RHS vector to the subproblem sp.

Arguments

• sp the subproblem

• rhs keyword argument key=value where value is a one-dimensional array containing the noise realisations

• constraint any valid JuMP @constraint syntax that includes the keyword defined by rhs

Examples

• @rhsnoise(sp, i=1:2, x + y <= i )

• @rhsnoise(sp, i=1:2, x + y <= 3 * rand(2)[i] )

@rhsnoises(sp, rhs, begin
    constraint
end)

Description

The plural form of @rhsnoise similar to the JuMP macro @constraints.

Arguments

See @rhsnoise.

Examples

@rhsnoises(sp, i=1:2, begin
    x + y <= i
    x + y <= 3 * rand(2)[i]
end)

setnoiseprobability!(sp::JuMP.Model, distribution::Vector{Float64})

Description

Set the probability distribution of the stagewise independent noise in the sp subproblem.

Arguments

• sp the subproblem

• distribution vector containing the probability of each outcome occuring. Should sum to 1. Defaults to the uniform distribution.

Examples

If there are two realizations:

• setnoiseprobability!(sp, [0.3, 0.7])

• setnoiseprobability!(sp, [0.5, 0.6]) will error!

@stageobjective(sp, kw=noises, objective)

Description

Define an objective that depends on the realization of the stagewise noise. objective can be any valid third argument to the JuMP @objective macro (i.e. @objective(sp, Min, objective)) that utilises the variable kw that takes the realizations defined in noises.

Examples

@stageobjective(sp, w=1:2, w * x)
@stageobjective(sp, i=1:2, w[i]^2 * x)
@stageobjective(sp, i=1:2, x[i])

@stageobjective(sp, objective)

Description

Define a deterministic objective.

Examples

@stageobjective(sp, x + y)

addconstraintnoise!(sp::JuMP.Model, x::JuMP.Variable, realizations::Vector{T}) where T

Add a stagewise-independent coefficient term into the model.

Important:

• Requires a solver that has implemented the MathProgBase.changecoeffs! method.

• Cannot be used if JuMP.solvehook is set (e.g., by SDDiP.jl).

If multiple terms have random coefficents, then the length of realizations must be the same in every case. This can also be used with stagewise-independent right-hand side terms (via @rhsnoise), again with equal numbers of realizations.

Example

If w ∈ [1,2,3] with equal probability, and we want to add the constraint: @constraint(sp, 2x + w*x <= 1) Then wx = addconstraintnoise!(sp, x, [1,2,3]) @constraint(m, 2x + wx <= 1)

Note: This is a bit of a hack. Given a term w*x in the model, for example, in a constraint such as 2x + w*x <= 1, we introduce a dummy variable and a dummy constraint so that: dummyconstraint: dummy_variable == w * x. This allows us to deterministically work around the fact that JuMP cannot modify the coefficient matrix.

AbstractRiskMeasure

Description

Abstract type for all risk measures.

modifyprobability!(measure::AbstractRiskMeasure,
        riskadjusted_distribution,
        original_distribution::Vector{Float64},
        observations::Vector{Float64},
        m::SDDPModel,
        sp::JuMP.Model
)

Description

Calculate the risk-adjusted probability of each scenario using the 'change-of-probabilities' approach of Philpott, de Matos, and Finardi,(2013). On solving multistage stochastic programs with coherent risk measures. Operations Research 61(4), 957-970.

Arguments

• measure::AbstractRiskMeasure

The risk measure

• riskadjusted_distribution

A new probability distribution

• original_distribution::Vector{Float64}

The original probability distribution.

• observations::Vector{Float64}

The vector of objective values from the next stage problems (one for each scenario).

• m::SDDPModel

The full SDDP model

• sp::JuMP.Model

The stage problem that the cut will be added to.

AVaR(beta::Float64)

The Average Value @ Risk measure. When beta=0, the measure is the is worst-case, when beta=1 the measure is equivalent to expectation.

ConvexCombination( (weight::Float64, measure::AbstractRiskMeasure) ... )

Create a weighted combination of risk measures.

Examples

ConvexCombination(
    (0.5, Expectation()),
    (0.5, AVaR(0.25))
)

Convex combinations can also be constructed by adding weighted risk measures together as follows:

0.5 * Expectation() + 0.5 * AVaR(0.5)

EAVaR(;lambda=1.0, beta=1.0)

Description

A risk measure that is a convex combination of Expectation and Average Value @ Risk (also called Conditional Value @ Risk).

λ * E[x] + (1 - λ) * AV@R(1-β)[x]

Keyword Arguments

• lambda

Convex weight on the expectation ((1-lambda) weight is put on the AV@R component. Inreasing values of lambda are less risk averse (more weight on expecattion)

• beta

The quantile at which to calculate the Average Value @ Risk. Increasing values of beta are less risk averse. If beta=0, then the AV@R component is the worst case risk measure.

Expectation()

The expectation risk measure.

DRO(radius::Float64)

The distributionally robust SDDP risk measure. Constructs a DRO risk measure object that allows probabilities to deviate by radius away from the uniform distribution.

WorstCase()

The worst-case risk measure.

AbstractCutOracle

Description

Abstract type for all cut oracles.

storecut!(oracle::AbstactCutOracle, m::SDDPModel, sp::JuMP.Model, cut::Cut)

Description

Store the cut cut in the Cut Oracle oracle. oracle will belong to the subproblem sp in the SDDPModel m.

validcuts(oracle::AbstactCutOracle)

Description

Return an iterable list of all the valid cuts contained within oracle.

allcuts(oracle::AbstactCutOracle)

Description

Return an iterable list of all the cuts contained within oracle, not just those that are returned by validcuts.

DefaultCutOracle()

Description

Initialize the default cut oracle.

This oracle keeps every cut discovered and does not perform cut selection.

LevelOneCutOracle()

Description

Initialize the cut oracle for Level One cut selection. See:

V. de Matos, A. Philpott, E. Finardi, Improving the performance of Stochastic Dual Dynamic Programming, Journal of Computational and Applied Mathematics 290 (2015) 196–208.

StaticPriceInterpolation(; kwargs...)

Constuctor for the static price interpolation value function described in

Gjelsvik, A., Belsnes, M., and Haugstad, A., (1999). An Algorithm for Stochastic Medium Term Hydro Thermal Scheduling under Spot Price Uncertainty. In PSCC: 13th Power Systems Computation Conference : Proceedings P. 1328. Trondheim: Executive Board of the 13th Power Systems Computation Conference, 1999.

Keyword arguments

• dynamics: a function that takes two arguments 1. price: a Float64 that gives the price in the previous stage. 2. noise: a single NoiseRealization of the price noise observed at the start of the stage. The function should return a Float64 of the price for the current stage.

• initial_price: a Float64 for the an initial value for each dimension of the price states.

• rib_locations: an AbstractVector{Float64} giving the points at which to discretize the price dimension.

• noise: a finite-discrete distribution generated by DiscreteDistribution

• cut_oracle: any AbstractCutOracle

Example

StaticPriceInterpolation(
    dynamics = (price, noise) -> begin
            return price + noise - t
        end,
    initial_price = 50.0
    rib_locations = 0.0:10.0:100.0,
    noise = DiscreteDistribution([-10.0, 40.0], [0.8, 0.2]),
)

DynamicPriceInterpolation(; kwargs...)

Constuctor for the dynamic price interpolation value function described in Downward, A., Dowson, O., and Baucke, R. (2018). On the convergence of a cutting plane method for multistage stochastic programming problems with stagewise dependent price uncertainty. Optimization Online.

Keyword arguments

• dynamics: a function that takes two arguments 1. price: a Float64 (if uni-variate) or NTuple{N,Float64} if multi-variate that gives the price in the previous stage. 2. noise: a single NoiseRealization of the price noise observed at the start of the stage. The function should return a Float64 (if uni-variate) or NTuple{N,Float64} if multi-variate that gives the price for the current stage.

• initial_price: a Float64 (if uni-variate) or NTuple{N,Float64} if multi-variate that gives the an initial value for each dimension of the price states.

• min_price: a Float64 (if uni-variate) or NTuple{N,Float64} if multi-variate that gives the minimum value of each dimension of the price states.

• max_price: a Float64 (if uni-variate) or NTuple{N,Float64} if multi-variate that gives the maximum value of each dimension of the price states.

• noise: a finite-discrete distribution generated by DiscreteDistribution

• lipschitz_constant: the maximum absolute subgradient of any price dimension in the domain bounded by min_price and max_price.

• cut_oracle: a DynamicCutOracle.

Examples

A uni-variate price process:

DynamicPriceInterpolation(
    dynamics = (price, noise) -> begin
            return price + noise - t
        end,
    initial_price = 50.0
    min_price = 0.0,
    max_price = 100.0,
    noise = DiscreteDistribution([-10.0, 40.0], [0.8, 0.2]),
    lipschitz_constant = 1e4
)

A multi-variate price process:

DynamicPriceInterpolation(
    dynamics = (price, noise) -> begin
            return (noise * price[1], noise * price[2] - noise)
        end,
    initial_price = (50.0, 50.0),
    min_price = (0.0,0.0),
    max_price = (100.0,100.0),
    noise = DiscreteDistribution([0.5, 1.2], [0.8, 0.2]),
    lipschitz_constant = 1e4
)

DiscreteDistribution{T}(observations::AbstractVector{T}, probabilities::AbstractVector{Float64})

Create a finite discrete distribution of observations supported with probability probabilities.

DiscreteDistribution{T}(observations::AbstractVector{T})

Create a finite discrete distribution of observations supported with uniform probability.

solve(m::SDDPModel; kwargs...)

Description

Solve the SDDPModel m using SDDP. Accepts a number of keyword arguments to control the solution process.

Positional arguments

• m: the SDDPModel to solve

Keyword arguments

• iteration_limit::Int: The maximum number of cuts to add to a single stage problem before terminating.

• time_limit::Real: The maximum number of seconds to compute for before termination. Defaults to Inf.

• simulation::MonteCarloSimulation: see MonteCarloSimulation

• bound_stalling::BoundStalling: see BoundStalling

• cut_selection_frequency::Int: Frequency (by iteration) with which to rebuild subproblems using a subset of cuts. Frequent cut selection (i.e. cut_selection_frequency is small) reduces the size of the subproblems that are solved, but incurrs the overhead of rebuilding the subproblems. However, infrequent cut selection (i.e. cut_selection_frequency is large) allows the subproblems to grow large (many constraints) leading to an increase in the solve time of individual subproblems. Defaults to 0 (never run).

• print_level::Int: 0 - off: nothing logged. 1 - on: solve iterations logged. 2 - verbose: detailed timing information is also logged. Defaults to 1

• log_file::String: Relative filename to write the log to disk. Defaults to "" (no log written)

• solve_type: One of

  • Asynchronous() - solve using a parallelised algorithm

  • Serial() - solve using a serial algorithm

  Default chooses automatically based on the number of available processors.

• reduce_memory_footprint::Bool: Implements the idea proposed in https://github.com/JuliaOpt/JuMP.jl/issues/969#issuecomment-282191105 to reduce the memory consumption when running SDDP. This is an issue if you wish to save the model m to disk since it discards important information. Defaults to false.

• cut_output_file::String: Relative filename to write discovered cuts to disk. Defaults to "" (no cuts written)

Returns

• status::Symbol: Reason for termination. One of

  • :solving

  • :interrupted

  • :converged

  • :iteration_limit

  • :bound_stalling

  • :time_limit

MonteCarloSimulation(;kwargs...)

Description

Collection of settings to control the simulation phase of the SDDP solution process.

Arguments

• frequency::Int

The frequency (by iteration) with which to run the policy simulation phase of the algorithm in order to construct a statistical bound for the policy. Defaults to 0 (never run).

• min::Float64

Minimum number of simulations to conduct before constructing a confidence interval for the bound. Defaults to 20.

• step::Float64

Number of additional simulations to conduct before constructing a new confidence interval for the bound. Defaults to 1.

• max::Float64

Maximum number of simulations to conduct in the policy simulation phase. Defaults to min.

• confidence::Float64

Confidence level of the confidence interval. Defaults to 0.95 (95% CI).

• termination::Bool

Whether to terminate the solution algorithm with the status :converged if the deterministic bound is with in the statistical bound after max simulations. Defaults to false.

BoundStalling(;kwargs...)

Description

Collection of settings to control the bound stalling convergence test.

Arguments

• iterations::Int

Terminate if the maximum deviation in the deterministic bound from the mean over the last iterations number of iterations is less than rtol (in relative terms) or atol (in absolute terms).

• rtol::Float64

Maximum allowed relative deviation from the mean. Defaults to 0.0

• atol::Float64

Maximum allowed absolute deviation from the mean. Defaults to 0.0

Asynchronous(; kwargs...)

Define

Type used to dispatch and control the behaviour of the asynchronous solution algorithm.

Arguments

• slaves::Vector{Int} the pid's of the slave processes. Defaults to workers()

• step::Float64 the number of iterations to complete before adding another slave. Used to replicated the scenario incrementation behaviour of V. de Matos,A. Philpott, E. Finardi, Improving the performance of Stochastic Dual Dynamic Programming, Journal of Computational and Applied Mathematics 290 (2015) 196–208.

Examples

Asynchronous() # load on all workers
Asynchronous(slaves=[2,3,4]) # load slaves on processes 2, 3, and 4
Asynchronous(step=10) # perform 10 iterations before adding new slave

Serial()

Define

Type used to dispatch the serial solution algorithm

simulate(m::SDDPPModel,variables::Vector{Symbol};
    noises::Vector{Int}, markovstates::Vector{Int})

Description

Perform a historical simulation of the current policy in model m.

noises is a vector with one element for each stage giving the index of the (in-sample) stagewise independent noise to sample in each stage. markovstates is a vector with one element for each stage giving the index of the (in-sample) markov state to sample in each stage.

Examples

simulate(m, [:x, :u], noises=[1,2,2], markovstates=[1,1,2])

results = simulate(m::SDDPPModel, N::Int, variables::Vector{Symbol})

Description

Perform N Monte-Carlo simulations of the current policy in model m saving the values of the variables named in variables at every stage.

results is a vector containing a dictionary for each simulation. In addition to the variables specified in the function call, other special keys are:

• :stageobjective - costs incurred during the stage (not future)

• :obj - objective of the stage including future cost

• :markov - index of markov state visited

• :noise - index of noise visited

• :objective - Total objective of simulation

All values can be accessed as follows

results[simulation index][key][stage]

with the exception of :objective which is just

results[simulation index][:objective]

Examples

results = simulate(m, 10, [:x, :u])
results[1][:objective] # objective of simulation 1
mean(r[:objective] for r in results) # mean objective of the simulations
results[2][:x][3] # value of :x in stage 3 in second simulation

getbound(m)

Description

Get the lower (if minimizing), or upper (if maximizing) bound of the solved SDDP model m.

SDDP.newplot()

Description

Initialize a new SimulationPlot.

SDDP.addplot!(p::SimulationPlot, ivals::AbstractVector{Int}, tvals::AbstractVector{Int}, f::Function; kwargs...)

Description

Add a new figure to the SimulationPlot p, where the y-value is given by f(i, t) for all i in ivals (one for each series) and t in tvals (one for each stage).

Keywords

• xlabel: set the xaxis label;

• ylabel: set the yaxis label;

• title: set the title of the plot;

• ymin: set the minimum y value;

• ymax: set the maximum y value;

• cumulative: plot the additive accumulation of the value across the stages;

• interpolate: interpolation method for lines between stages. Defaults to "linear" see the d3 docs

for all options.

Examples

results = simulate(m, 10)
p = SDDP.newplot()
SDDP.addplot!(p, 1:10, 1:3, (i,t)->results[i][:stageobjective][t])

show(p::SimulationPlot)

Launch a browser and render the SimulationPlot plot p.

 SDDP.plotvaluefunction(m::SDDPModel, stage::Int, markovstate::Int, states::Union{Float64, AbstractVector{Float64}}...; label1="State 1", label2="State 2")

Description

Plot the value function of stage stage and Markov state markovstate in the SDDPModel m at the points in the discretized state space given by states. If the value in states is a real number, the state is evaluated at that point. If the value is a vector, the state is evaluated at all the points in the vector. At most two states can be vectors.

Examples

SDDP.plotvaluefunction(m, 2, 1, 0.0:0.1:1.0, 0.5, 0.0:0.1:1.0; label1="State 1", label2="State 3")

getsubproblem(m::SDDPModel, t::Int, i::Int)

Get the subproblem in stage t and Markov state i from the SDDPModel m.

writecuts!(filename::String, m::SDDPModel; onlyvalid=false)

Writes all cuts from model m to filename.

If onlyvalid is true, write the cuts returned from validcuts, else write the cuts returned from allcuts.

loadcuts!(m::SDDPModel, filename::String)

Load cuts from the file created using the cut_output_file argument in solve.

Example

m = SDDPModel() do ... end
status = solve(m; cut_output_file="path/to/m.cuts")`
m2 = SDDPModel() do ... end
loadcuts!(m2, "path/to/m.cuts")

SDDP.savemodel!(filename::String, m::SDDPModel)

Save the SDDPModel m to the location filename. Can be loaded at a later date with m = SDDP.loadmodel(filename).

Note: this function relies in the internal Julia Base.serializefunction. It should not be relied on to save an load models between versions of Julia (i.e between v0.5 and v0.6). For a longer-term solution, see SDDP.loadcuts! for help.

loadmodel(filename::String)

Load a model from the location filename that was saved using SDDP.savemodel!.

Note: this function relies in the internal Julia Base.serializefunction. It should not be relied on to save an load models between versions of Julia (i.e between v0.5 and v0.6). For a longer-term solution, see SDDP.loadcuts! for help.