# Policy Graph in SDDP.jl package

**URL:** <https://discourse.julialang.org/t/policy-graph-in-sddp-jl-package/100062>\
**Category:** Optimization (Mathematical)\
**Tags:** question, optimization\
**Created:** [June 8, 2023, 4:26pm UTC](https://discourse.julialang.org/t/policy-graph-in-sddp-jl-package/100062 "2023-06-08T16:26:13Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![Sorooshsa](https://avatars.discourse-cdn.com/v4/letter/s/977dab/32.png) [@Sorooshsa](https://discourse.julialang.org/u/Sorooshsa)\
**Post date:** [June 8, 2023, 4:26pm UTC](https://discourse.julialang.org/t/policy-graph-in-sddp-jl-package/100062/1 "2023-06-08T16:26:13Z")

</div>

Hi,  
I know that there are a few options for making the graph of our problem while we use SDDP.jl e.g. linear policy graph, Markov policy graph.  
I have two questions:

1. What is the difference between the Linear and Markov policy graph?
2. Based on the theory of stochastic optimization, we can use SDDP only if the problem is stage-wise independent (in other words, the process is Markovian). So, what does it mean to choose the type of policy graph? Does it mean our process is not Markovian if we choose the linear policy graph? Does it mean there is a linear relation between stages if we choose the linear policy graph? So, this process is not stagewise independent anymore? Then, without meeting the required condition, SDDP cannot be applied.

Best,  
Soroosh

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [June 8, 2023, 9:03pm UTC](https://discourse.julialang.org/t/policy-graph-in-sddp-jl-package/100062/2 "2023-06-08T21:03:47Z")

</div>

Hi @Sorooshsa, let me take a stab at these questions:

> What is the difference between the Linear and Markov policy graph?

A linear policy graph is a graph in which the nodes form a linear graph. A Markovian policy graph is a graph in which the nodes form a Markov chain. You might want to read [https://github.com/odow/SDDP.jl/blob/master/papers/policy\_graph/preprint.pdf](https://github.com/odow/SDDP.jl/blob/master/papers/policy_graph/preprint.pdf) or [Markovian policy graphs · SDDP.jl](https://odow.github.io/SDDP.jl/stable/tutorial/markov_uncertainty/).

> Based on the theory of stochastic optimization, we can use SDDP only if the problem is stage-wise independent

Stagewise-independent is a misnomer. It really should be “nodewise-independent.” By construction, all policy graphs that you can formulate using SDDP.jl are node wise independent and meet the assumptions for our SDDP algorithm.

> So, what does it mean to choose the type of policy graph

You should choose the graph to best model your problem. If you have an independent random variable in each stage, you ca use a linear policy graph. If you stochastic process can be modeled by a Markov chain, use that. It’s hard to offer advice in general. (You could open an issue at SDDP.jl with the beginnings of a reproducible example if you want more specific help.) You might want to read [Example: the milk producer · SDDP.jl](https://odow.github.io/SDDP.jl/stable/tutorial/example_milk_producer/).

> Does it mean our process is not Markovian if we choose the linear policy graph?

No. The linear graph is a special case of a Markov chain in which there is one Markov state in each stage.

> Does it mean there is a linear relation between stages if we choose the linear policy graph?

‘Linear’ and ‘Markovian’ come from the structure of the graph, not whether the subproblems are linear.

> So, this process is not stagewise independent anymore? Then, without meeting the required condition, SDDP cannot be applied.

Pretend you never heard the term stagewise-independent. I don’t find it useful, and it only gets people confused. SDDP.jl works on a policy graph, which is just a graph of subproblems, and there is a random variable at each node.

---

<div class="post-metadata">

**Author:** ![WalterMadelim](https://avatars.discourse-cdn.com/v4/letter/w/3e96dc/32.png) [@WalterMadelim](https://discourse.julialang.org/u/WalterMadelim)\
**Post date:** [December 3, 2025, 4:19am UTC](https://discourse.julialang.org/t/policy-graph-in-sddp-jl-package/100062/3 "2025-12-03T04:19:48Z")

</div>

> [@odow](#):
>
> Stagewise-independent is a misnomer. It really should be “nodewise-independent.”

Not fully agree. The notion of “stage” is more fundamental and intrinsic. The notion “node” embodies an implication/restriction—you are restricting the underlying true stochastic process to be a scenario tree.

Now I want to ask:

- is it possible to carry out a SDDP algorithm even if we do not pre-construct a finite scenario tree? (e.g. we only provide a sampler, will this be sufficient?)

One more question related: [Markovian SDDP: is a finite and concrete scenario tree necessary?](https://discourse.julialang.org/t/markovian-sddp-is-a-finite-and-concrete-scenario-tree-necessary/134317)

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [December 3, 2025, 4:59am UTC](https://discourse.julialang.org/t/policy-graph-in-sddp-jl-package/100062/4 "2025-12-03T04:59:08Z")

</div>

Please prefer to start a new thread instead of reviving an old question.