How do I check convergence in stochastic Benders?

Question

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?

Answer 1

Let the objective of the master problem (the first-stage problem of stochastic programming) be

\begin{align} \text{Minimize}~ cx + \frac{1}{|S|} \sum_{s \in S} \theta_s \end{align}

where $\theta_s$ approximates the second-stage objective by Benders optimality cuts gradually.

Then let the objective of the $s$th sub problem (the second-stage problem of stochastic programming) be

\begin{align} \text{Minimize}~ d_s y_s \end{align}

which are solved by fixing the fist-stage decisions to $\bar{x}$.

The Benders algorithm terminates when

\begin{align} c \bar{x} + \frac{1}{|S|} \sum_{s \in S} \bar{\theta_s} = c \bar{x} + \frac{1}{|S|} \sum_{s \in S} d_s y_s \end{align}

The global optimum is reached when (i) the first-stage solution is feasible for all the scenarios; (ii) the objective of the master problem and the subproblems meet the requirement specified by the above equation.