Interpolating between nodes in the graph

[odow]

Hello Oscar, I'd like to open this issue to ask about the possibility of interpolating the cut for an out-of-sample price point instead of using the cut from the closest price node as in Gjelsvik et al., 2010. Is this interpolation possible in SDDP.jl?
Thank you for your time.

Originally posted by @Remmy195 in #707

[odow]

This is exactly what the objective state stuff does:

• https://sddp.dev/stable/tutorial/objective_states/
• https://optimization-online.org/2018/02/6454/

The improvement over existing is that it interpolates during training as well as during evaluation.

The downside is that it is more computationally challenging, and there are some limitations about what price process you can use, etc.

We don't have a way to implement interpolation for normal graphs. One suggestion would be to dump the cuts to file and manually build a set of new subproblems with the correct interpolation weights.

One reason I haven't added this is that, although it seems simple in theory if you have a Markovian policy graph that represents a univariate price process, SDDP.jl supports much more general graphs, and all we see is a collection of nodes. We know what happens within a node, what parameterize does etc. We could add something, but it would require a lot of user input and decisions. And this is a pretty infrequent request. My main suggestion would be to just use the nearest price node, and train with more nodes if the policy is not sufficient.

[Remmy195]

I've looked at the objective state but have not implemented it because my price process is nonparametric so I have generated scenarios outside the model. Also setting the required parameters for the objective state (especially the lipschitz constant) is something I haven't been able to define yet.

I think using more nodes in the policy graph will perform well for the out-of-sample simulation; just at the expense of more computation.

Thank you!

[odow]

I think using more nodes in the policy graph will perform well for the out-of-sample simulation; just at the expense of more computation.

👍

Re computation time: we now support multi-threading, which is particularly effective with graphs with many nodes:
https://sddp.dev/stable/apireference/#SDDP.Threaded

[Remmy195]

Ha nice! regarding parallelization; I've tried SDDP.Asynchronous() in the past but didn't get good solutions. I'll try SDDP.Threaded().

[odow]

Yeah I should remove mention of SDDP.Asynchronous from the docs. No one should use it.

[odow]

I'm tempted to close this as "won't-fix". I don't think I plan to add interpolation between nodes.

I've removed mention of Asynchronous from the docs and replaced it with Threaded in #821: https://sddp.dev/dev/guides/improve_computational_performance/#Parallelism

[Remmy195]

I just want to note that I tested SDDP.Threaded(), and it was much faster with good solution. Thanks

[odow]

and it was much faster with good solution. Thanks

No problem 😄

[SolidAhmad]

Yeah I should remove mention of SDDP.Asynchronous from the docs. No one should use it.

Hi Oscar, how come? Did the asynchronous scheme fail to show a tangible benefit? Does this mean SDDP.threaded() strictly uses the synchronous scheme?

[odow]

Threaded is a different algorithm that uses multithreading instead of distributed parallelism. See https://jump.dev/JuMP.jl/stable/tutorials/algorithms/parallelism/

In my experience, the Asynchronous algorithm had a number of limitations:

• Each process required a complete copy of the model, so if you use N processors then you needed N times the memory.
• The memory limitation meant it was useful only on something like an HPC with a large amount of memory. It did not work on a laptop
• There was a lot of interprocess communication overhead as each process shared its cuts with other processes and added the cuts found by other processes.
• Because of the communication delays and the iterative nature of the algorithm, two separate processes could often find the "same" cuts, which is wasted work

The new Threaded algorithm fixes all of these limitations:

• Because it uses multithreading, it has a single copy of the model. N threads do not need more memory than 1 thread
• It works best on a laptop, where we are not trying to scale over multiple separate machines
• There is no interprocess communication because every thread modifies the same copy of the model
• All threads always use the most up-to-date value functions in every iteration, so no work is repeated.

The downside of the Threaded algorithm is that it is limited to a single physical machine (we can no longer parallelize across multiple nodes), and it is also limited by the number of nodes in the graph (we cannot use more threads than the # of nodes in the graph).

[SolidAhmad]

The downside of the Threaded algorithm is that it is limited to a single physical machine (we can no longer parallelize across multiple nodes), and it is also limited by the number of nodes in the graph (we cannot use more threads than the # of nodes in the graph).

Thank you for the thorough clarification!