1
$\begingroup$

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?

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you, that helps! $\endgroup$ Oct 13, 2023 at 10:05

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.