multi stage stochastic programming algorithm

Question

I have a multi-stage stochastic programming model. I have 3 groups of variables: the first group takes values at the beginning of the planning horizon before the first realization and does not change until the end of the planning horizon and has no t index (they are binary and continuous), the second option is “here and now” variables that before each realization Are taken value and are continuous, the third group are “wait and see” variables that take value after each realization (binary and continuous). The model is SMINLP. I converted it to SMILP through linearization and solved it by CPLEX solver with generating a small number of scenarios . I want to consider a continuous distribution for the stochastic parameter and generate a large number of scenarios by sampling and run an algorithm for it. nested benders decomposition or progressive hedging algorithms are more efficient for this model? If anyone has experience, thank you in advance for your help.

Answer 1

If your question is “Are nested Benders decomposition or progressive hedging more efficient than solving a very large-scale monolithic formulation (sometimes called ‘deterministic equivalent’) with CPLEX?”, the answer is very likely a clear “Yes, if you get the implementation right”.

If the question is “Is nested Benders decomposition or progressive hedging more efficient to solve a large stochastic program?”, i.e., you want to decide between the two, the answer is unclear to me, but likely a lot more intricate and intuitively I would expect the answer to be “If you want to be really sure you’d have to try both with your model.” I am not too familiar with PHA, so take my intuition with a grain of salt.

A couple of general remarks:

• Decomposition algorithms have demonstrated their ability to solve large-scale problem instances that could not be solved as monolithic formulations. That does not mean they can solve arbitrarily large problems! In fact, by just starting to model from scratch it is still very easy to come up with a formulation that is too large to be solved with all the techniques we have available today. I would recommend to gradually increase the problem size (in your case by increasing the number of samples gradually) until you hit the boundary of what CPLEX can solve as monolithic formulation. Then, decomposition algorithms will provide you with a juicy speedup, allowing you to gradually increase the number of samples further, until also decomposition algorithms are pushed to their limits.

• As far as I understand, progressive hedging algorithms copy also the non-scenario specific variables for each scenario, i.e., instead of just one variable $x$, the algorithm works with $x_s, \forall s \in \{ S \}$ and penalizes non-implementability, so the violation of $x_s = x_{s’} \forall s \neq s’$. If you have many such variables $x$, copying them all for all scenarios may blow up the problem size even more, whereas BD does not need these copies.

• BD is notoriously hard to implement in practise, as Steve Maher wrote about on his blog which occurs to be offline. Another resource I can recommend for its accessibility is Arthur Maheos blog

Hope this helps!