Benchmarks and ideas

[odow]

Hi there,

Nice work. Because of https://github.com/odow/SDDP.jl, I'm always interested to see other SDDP implementations.

Do you have any benchmark results on the different Lagrangian methods, or on the non-convex stuff? I don't have access to Gurobi, so I can't test this unfortunately. Also interested to know whether you tried the Lagrangian cuts without binarizing. You'll end up with a potentially sub-optimal policy, but sometimes it can still perform quite well.

[leoschleier]

Hi @odow , thank you for sharing your ideas. Great to see that my repository caught your attention.

I haven't tried Lagrangian cuts without binarizing, but this would be interesting for comparison. The non-convex Lagrangian cuts increase the complexity of the subproblems quite significantly. Therefore, I keep their number small and combine them with strengthened Benders cuts. I will let you know once I have presentable results.

Unfortunately, the time I can work on this project is very limited. I plan to refactor the project so the model and the algorithm aren't strongly coupled and that Gurobi is replaceable with another solver. In general, the package still needs to be more user-friendly.

[odow]

The non-convex Lagrangian cuts increase the complexity of the subproblems quite significantly

Yeah. This is my conclusion: https://github.com/odow/SDDP.jl/issues/609#issuecomment-1541843164.

I see Vattenfall on your LinkedIn, so here's something you might be interested in.

We're currently working on a thing which I think is very cool: using different models in the forward and backward passes.

The idea is that you want an accurate non-convex simulator in the forward pass (for example, accurate production as a value of the reservoir head), and then in the backward pass you use a convex approximation to generate cuts (for example, a constant head approximation).

See

• https://github.com/odow/SDDP.jl/pull/611
• https://ieeexplore.ieee.org/document/9521833

[tys12]

Hello, I have preliminarily learned sddip algorithm, can you explain the function of each file in more detail?

[ChrisFuelOR]

Hi @odow,

@leoschleier and I are working on this project together. Whereas he has not tried out Lagrangian cuts without binarization for the application he is working on, I have tried this for some problems using my similar, yet slightly different DynamicSDDiP.jl repository in Julia. I'm still working on finishing my tests, but I hope that I can publish the results soon.

On another note, your idea on using separate models in forward and backward pass sounds really interesting. Will you (or one of your co-authors) attend ICSP in July? If so, I'm open to have some more detailed discussion there.

[odow]

Will you (or one of your co-authors) attend ICSP in July?

I'm not. But I assume the PUC-Rio gang of Alexandre Street et al will be there. You should talk to them.

Here's a tutorial for the forward models: https://odow.github.io/SDDP.jl/stable/tutorial/pglib_opf/. If you have some thoughts, you could open an issue at SDDP.jl and we can discuss there. (Or email me.)

[odow]

@tys12

can you explain the function of each file in more detail?

This is a pretty difficult request and not one you're likely to get an in-depth answer on.

If you just want to solve some multistage stochastic integer models, you might want to take a look at https://github.com/odow/SDDP.jl instead.

sddip algorithm

You might want to read https://odow.github.io/SDDP.jl/stable/guides/add_integrality/ for my opinion on whether "SDDiP" is a distinct algorithm.

[odow]

@leoschleier here's something else you might be interested in: you can formulate the "should I do an iteration of Benders, strengthened Benders, or Lagrangian" as a multi-armed bandit problem.

https://github.com/odow/SDDP.jl/blob/3de99e109ca47df4bb2f09f3cf55e7f54d9b08b6/src/plugins/duality_handlers.jl#L315-L419