So in the deterministic version of Benders, the main process works like this:
I initialize my x-vector (Integer variables from the master problem) and solve the dual subproblem (SP).
I add an optimality cut/feasibility cut to the master problem (MP), depending on if the SP was unbounded or optimal.
Then I resolve the MP, pass that solution again to the SP and repeat this until the objective value of the MP = objective of the SP.
Now, I want to tackle the stochastic version of Benders.
For this, I now have different scenarios and the process looks like this:
I initialize the algorithm with a MP solution. I pass that on to the SPs, one per scenario.
I solve the SP for each scenario. I add cuts to the MP the same as before:
- feasibility cut if the SP is unbounded
- optimality cut if the SP is optimal but not globally optimal
Now, I struggle with my implementation because I don't understand how the stopping criteria of the algorithm works. How do I check global optimality when I don't have "one" solution value anymore for the SP? (Since I can't check MP = SP)
And if for one scenario, the SP is globally optimal, what do I do? Do I just skip it and go to the next scenario? Or do I skip the whole iteration?
Overall, what is the stopping criteria for the stochastic version of Benders?