1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Jun 22, 2023 at 14:50
  • $\begingroup$ Check here odow.github.io/SDDP.jl/stable. @Oscar $\endgroup$ Jun 22, 2023 at 19:29
  • $\begingroup$ Nested Benders is not necessarily deterministic. $\endgroup$ Jun 26, 2023 at 5:29

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ So is HiGHS linear programming solver deterministic $\endgroup$ Jun 26, 2023 at 5:55
  • $\begingroup$ and if it is deterministic then can I say that nested benders decomposition deterministic $\endgroup$ Jun 26, 2023 at 5:58
  • $\begingroup$ You can't say anything based on the theoretical algorithm. It depends on your actual implementation. $\endgroup$ Jun 26, 2023 at 8:55
  • $\begingroup$ Just run your problem multiple times and see if you get different sequences of iterates. $\endgroup$ Jun 26, 2023 at 8:56
  • $\begingroup$ See also or.stackexchange.com/questions/8892/… $\endgroup$ Jun 26, 2023 at 8:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.