search

odow / SDDP.jl

Stochastic Dual Dynamic Programming in Julia
https://sddp.dev
Other
289 stars 60 forks source link

Implement MIDAS on SDDP.jl #609

Closed caioluke closed 1 year ago

caioluke commented 1 year ago

Hi Oscar,

I have recently fallen in love with your package (it took me a while but it finally hit on me!) and I would like to contribute to it.

One ideia that came to my mind was to implement the MIDAS algorithm (step-cuts) to handle integrality in SDDP.

Here's the paper: https://www.epoc.org.nz/papers/PhilpottWahidBonnansR1.pdf

Do you think that it would be worth the time to do it?

If you have any other more useful features to be implemented in the pipeline I suppose we could talk about them.

Here's my email: caioluke97atgmaildotcom

Thank you for the amazing work!

odow commented 1 year ago

it took me a while but it finally hit on me!

Woo!

One ideia that came to my mind was to implement the MIDAS algorithm (step-cuts) to handle integrality in SDDP

At one point (many versions ago), I had everything set up for this. I had an AbstractValueFunction type, with various plugins for changing the type of the cuts that were added with the view to incorporating MIDAS etc: https://github.com/odow/SDDP.jl/blob/8c0435dd25f5f163a84a0693c0df10966cb4a0ae/src/defaultvaluefunction.jl#L11

But my conclusion from MIDAS, SLDP, NCNBD, and all the other non-convex cut algorithms is that they don't work. Fundamentally, they change the problem from scaling as a LP to scaling as a MIP, and that's something that can never be overcome. Second, the structure of the cuts mean that you're always cutting some small epsilon off the cost-to-go. Andy and Faisal used to say that MIDAS was "marching up the monotone" because it would add lots of little steps epsilon apart, instead of a few well-placed steps.

Even SDDiP with Lagrangian cuts performs terribly, and I don't encourage anyone to use it (https://odow.github.io/SDDP.jl/stable/guides/add_integrality/#Does-SDDP.jl-implement-the-SDDiP-algorithm?). Fundamentally, you go from 1 LP solve to get a dual, to N MILP solves. That's something an order or magnitude or more expensive. I could have generated a lot of cuts for the same amount of time...

I think people are faaaaar better off exploring ways to simulate the forward pass of model with a detailed integer/non-convex model of the dynamics, and use a relaxation for the backward pass.

I'll point you to:

Andrew's paper is, I think, woefully under-explored in the community. I'd like to see lots of things like it: develop an accurate simulation of the model, and then you treat SDDP as a heuristic to find good policies, instead of treating the SDDP model as the real world that you're trying to solve to optimality.

Do you think that it would be worth the time to do it?

So no :smile: I don't think so, and I won't be adding non-convex cuts to SDDP.jl.

If you want to play around, I'll post in https://github.com/odow/SDDP.jl/issues/419 with something that I was just thinking over. You have very co-incidental timing...

caioluke commented 1 year ago

Ha! Funny coincidence.

Thanks for the input. I suppose I fell into the trap of wanting to get the best I can get from a model (its optimum) while forgetting that my model has a reality gap, therefore the best it can provide is not necessarily the best solution for my real life application!

"Ceci n'est pas une pipe" as Magritte once said.

Ok, I'll have a look at #419 and try to implement it soon enough. :)

odow commented 1 year ago

I suppose I fell into the trap of wanting to get the best I can get from a model (its optimum) while forgetting that my model has a reality gap, therefore the best it can provide is not necessarily the best solution for my real life application!

:100: I don't think you're the only one 😆 But I think to make progress and encourage this, SDDP.jl needs to provide some tooling like #419.

odow commented 1 year ago

Thanks for the suggestion. But I think I'm going to close this as "won't-fix."

Feel free to open any other issues with suggestions :smile:

odow commented 1 year ago

@caioluke if you're interested, take a look at https://github.com/odow/SDDP.jl/pull/611