Is stochastic dual dynamic programming (SDDP) a deterministic solution algorithm or does it have a stochastic component to it?

Question

I am currently working on a paper in which I am statistically comparing dynamic optimization algorithms like SDDP, Actor-Critics etc. In this regard, should I be running SDDP algorithm for my deterministic multi-stage optimization problem once (if it is a deterministic solver) or should I be running it multiple times (like 50 times in case it has a stochastic component to it)?

It is very important to note that my problem is a deterministic (not stochastic) multi stage optimization problem, meaning it has only one scenario.

SDDP for single scenario problem is just nested Benders. So it is deterministic in your case. However, for more general problems (multiple-scenarios ones), it is stochastic, since it involves sampling. — Penghui Guo, Jun 22 '23 at 14:50

Oscar Dowson · Accepted Answer · 2023-08-30T22:15:31.840

2

It depends on the implementation.

Irrespective of whether the model has one scenario or many, it's possible to code an implementation of SDDP that is deterministic in the sense that it will return the same optimal policy if run multiple times with the same random seed.

It's also possible to code an implementation that is stochastic and potentially returns different optimal policies each time.

Even if your SDDP code is deterministic, it also depends on whether the underlying optimization solver is reproducible. For example, in Gurobi's default configuration it may choose a non-deterministic concurrent algorithm when solving an LP: https://www.gurobi.com/documentation/10.0/refman/method.html This can cause you to visit a different sequence of states in the forward pass and add a different sequence of cuts.

edited Aug 30 '23 at 22:15

answered Jun 26 '23 at 05:28

Oscar Dowson

971
5
6

So is HiGHS linear programming solver deterministic – Engr. Moiz Ahmad Jun 26 '23 at 05:55
and if it is deterministic then can I say that nested benders decomposition deterministic – Engr. Moiz Ahmad Jun 26 '23 at 05:58
You can't say anything based on the theoretical algorithm. It depends on your actual implementation. – Oscar Dowson Jun 26 '23 at 08:55
Just run your problem multiple times and see if you get different sequences of iterates. – Oscar Dowson Jun 26 '23 at 08:56
See also https://or.stackexchange.com/questions/8892/are-optimization-results-stochastic – Oscar Dowson Jun 26 '23 at 08:58
I have run my algorithm multiple times with different seeds and I am getting the same results every time. In fact, the implementation is of SDDP.jl in julia, the impressive code you developed – Engr. Moiz Ahmad Jun 26 '23 at 11:24
Then yes, for this particular case, SDDP.jl + single scenario + HiGHS is deterministic. – Oscar Dowson Jun 26 '23 at 22:13
ok great thankyou very much – Engr. Moiz Ahmad Jun 27 '23 at 04:48

Is stochastic dual dynamic programming (SDDP) a deterministic solution algorithm or does it have a stochastic component to it?

1 Answers1