DOCSEARCHbyAlgolia
Submit Docs

SDDP.jl

repository·master·Indexed 43 days ago

https://github.com/odow/sddp.jl

A Julia extension for the JuMP modeling language designed to solve large-scale convex multistage stochastic programming problems using the Stochastic Dual Dynamic Programming (SDDP) algorithm. It provides tools for graph construction (e.g., LinearGraph, MarkovianGraph), risk measure integration (AVaR, CVaR, Entropic), and various sampling and parallel execution schemes.

Tokens
16.3K
Snippets
43
Records
67
Agent score
56%

What's inside SDDP.jl

  1. Overview of SDDP.jl

    master
    SDDP.jl is a Julia extension for the JuMP modeling language. It is designed to solve large-scale convex multistage stochastic programming problems using the Stochastic Dual Dynamic Programming (SDDP) algorithm.

  2. Overview of SDDP.jl capabilities

    master

    SDDP.jl is a package for solving large convex multistage stochastic programming problems using stochastic dual dynamic programming. It is designed to be flexible by leveraging the JuMP modeling language.

    Key advanced features include support for:

    • Infinite horizon problems (using policy graph decomposition)
    • Convex risk measures (including entropic risk measures)
    • Mixed-integer state and control variables
    • Partially observable stochastic processes
    • Objective states (stagewise-dependent objective uncertainty)
    • Bi-objective optimization

  3. How SDDiP-style duality works in SDDP.jl

    master

    SDDiP (Stochastic Dual Dynamic Integer Programming) focuses on computing subgradients for discrete problems. In SDDP.jl, you can implement the Lagrangian duality approach to obtain these subgradients by using SDDP.LagrangianDuality as your duality_handler in SDDP.train.

    Note that Lagrangian duality is computationally intensive because it requires solving many mixed-integer programs rather than a single linear program, which can lead to poor performance compared to standard LP-based duality.

    SDDP.train(
    model;
    duality_handler = SDDP.LagrangianDuality(),
)

  4. How to access variables from a previous stage

    master

    To use a variable from a previous stage in a constraint or objective function, that variable must be declared as a state variable using SDDP.State.

    When a variable is marked as SDDP.State, SDDP manages its transition between stages using .in and .out attributes:

    • variable.in: The value of the variable at the beginning of the current stage (carried over from the previous stage).
    • variable.out: The value of the variable at the end of the current stage (to be passed to the next stage).

    Important Requirement: You must initialize the same number of state variables in every stage, even if they are not used in a specific stage.

    # Example of state variable declaration
@variable(sp, reservoir >= 0, SDDP.State, initial_value = 0)

# Using the state variable in a constraint
@constraint(sp, reservoir.out == reservoir.in + inflow - outflow)

  5. Graph types and construction

    master

    SDDP.jl uses various graph types to represent stochastic programs. You can construct graphs using functions like SDDP.add_node, SDDP.add_edge, and SDDP.add_ambiguity_set.

    Key graph types include:

    • SDDP.LinearGraph
    • SDDP.MarkovianGraph
    • SDDP.UnicyclicGraph
    • SDDP.LinearPolicyGraph
    • SDDP.MarkovianPolicyGraph
    • SDDP.PolicyGraph

  6. Choose between single-cut and multi-cut SDDP

    master

    SDDP.jl supports two methods for creating cuts. The choice depends on your problem structure:

    • Single-cut (Default): Generally performs better when the number of realizations of the stagewise-independent random variable is large.
    • Multi-cut: Generally performs better on smaller problems. Warning: Multi-cut can cause numerical stability issues, especially when used with objective or belief state variables.

    Switch between these methods using the cut_type argument in SDDP.train.

    SDDP.train(model; cut_type = SDDP.SINGLE_CUT)
SDDP.train(model; cut_type = SDDP.MULTI_CUT)

  7. How to choose the number of threads for SDDP.jl

    master

    When deciding how many threads to allocate, follow these guidelines to avoid performance degradation:

    1. Physical Cores: Choose a number of threads less than or equal to the number of physical cores on your machine.
    2. Graph Nodes: The number of threads is upper-bounded by the number of nodes in your policy graph. If your graph has 3 nodes, SDDP.jl will not use more than 3 threads, even if you requested more.
    3. Avoid Over-subscription: Using more threads than physical cores (e.g., requesting 52 threads on a 4-core laptop) will likely lead to poor performance, even if the graph has enough nodes to support them.

  8. Understanding convergence with discrete variables

    master
    When models contain discrete variables, SDDP.jl cannot guarantee convergence to a globally optimal policy. However, in practice, the algorithm often finds integer-feasible policies that perform well in simulation. For large graphs or high uncertainty, finding a globally optimal policy is computationally difficult for most algorithms.

  9. Automatically create a Markovian graph from a stochastic process

    master

    SDDP.jl can automatically discretize a one-dimensional stochastic process and fit a Markov chain. To do this, pass a function that returns a Vector{Float64} (representing a realization of the process) to SDDP.MarkovianGraph.

    Required keyword arguments:

    • budget: The total number of nodes in the resulting Markovian graph.
    • scenarios: The number of realizations of the simulator function used to approximate the graph.
    using SDDP

# A function representing a stochastic process
function simulator()
    scenario = zeros(5)
    for i = 2:5
        scenario[i] = scenario[i - 1] + rand() - 0.5
    end
    return scenario
end

# Create a PolicyGraph using the automatic Markovian construction
model = SDDP.PolicyGraph(
    SDDP.MarkovianGraph(simulator; budget = 10, scenarios = 100),
    sense = :Max,
    upper_bound = 1e3
) do subproblem, node
    (stage, price) = node
    @variable(subproblem, x >= 0, SDDP.State, initial_value = 1)
    @constraint(subproblem, x.out <= x.in)
    @stageobjective(subproblem, price * x.out)
end

  10. Add multi-dimensional state variables to an SDDP model

    master

    In SDDP.jl, you can define containers of state variables within a LinearPolicyGraph using standard JuMP syntax. By passing SDDP.State as the variable type in the @variable macro, you enable the state-dependent features of SDDP. This supports scalar variables, vectors, and multi-dimensional containers like JuMP.Containers.DenseAxisArray.

    using SDDP, HiGHS

model = SDDP.LinearPolicyGraph(
           stages=1, lower_bound = 0, optimizer = HiGHS.Optimizer
       ) do subproblem, t
           # A scalar state variable.
           @variable(subproblem, x >= 0, SDDP.State, initial_value = 0)
           
           # A vector of state variables.
           @variable(subproblem, y[i = 1:2] >= i, SDDP.State, initial_value = i)
           
           # A JuMP.Containers.DenseAxisArray of state variables.
           @variable(subproblem, z[i = 3:4, j = [:A, :B]] >= i, SDDP.State, initial_value = i)
       end

  11. Evaluate and visualize results

    master

    After training, you can evaluate the policy and visualize performance:

    • SDDP.simulate: Run a simulation using the trained policy.
    • SDDP.evaluate: Evaluate the SDDP.ValueFunction or a SDDP.PolicyGraph against SDDP.ValidationScenarios.
    • SDDP.plot: Plot results.
    • SDDP.SpaghettiPlot: Create spaghetti plots using SDDP.add_spaghetti.
    • SDDP.publication_plot: Create plots suitable for publication.

  12. Install and load SDDP.jl

    master

    To use SDDP.jl, load the package using the using SDDP command. Note that SDDP only exports the @stageobjective macro. All other functions and types must be accessed using the SDDP. prefix.

    using SDDP

# All other calls must be prefixed with SDDP.
SDDP.train(...)