Assuming I have a stochastic MIP that I want to minimize using Benders' Decomposition.

With the objective of the MP being:

$$ Minimize \; cx + \frac{1}{\lvert S \rvert} \sum_{s \in S} \theta_s $$

where $\theta_s$ approximates the second-stage objective.

The objective of the $s$th SP is:

$$ Minimize \; d_s y_s $$

And the dual version of that:

$$ Maximize \; \pi^T (h_s - T_s \bar{x}) $$

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

Using Benders' Decomposition, obviously I can keep track of the LB vs. UB by comparing the results of the MP and the SPs, with the MP being a LB on the original MIP and the sum of the SPs being a UB.

If LB = UB, the algorithm terminates:

$$ c\bar{x} + \frac{1}{\lvert S \rvert} \sum_{s \in S} \bar{\theta}_s = c\bar{x} + \frac{1}{\lvert S \rvert} \sum_{s \in S} d_s y_s $$

Now, if I use the Alternative Cut Generation Problem as proposed by Fischetti et al. (2010) , I transform my SPs with the aim to find deeper cuts:

$$ Maximize \; \pi^T (h_s - T_s \bar{x}) - \theta_s \pi_0 $$

But now, the SPs, due to this transformation, will have much smaller values.

At this point, I am unsure how to calculate the UB that the SPs construct.

Considering we basically scaled the $\pi$-variables by using $\pi_0$, due to the L1 normalization of the $\pi$-variables.

Is it a simple as adding back $ + \theta_s \pi_0 $ and then dividing that result by $\pi_0$ to "revert" the normalization of the dual variables?


1 Answer 1


The fundamental principle you need is that, for minimization problems, upper bounds come from feasible solutions. Given $\bar{x}$, the subproblems try to find a complete feasible solution with $x=\bar{x}$. Whether you compute a primal or dual form of each subproblem $s$, you want to extract a primal feasible solution $\bar{y}_s$, and then the true objective value of the resulting complete feasible solution is your upper bound: $$c\bar{x}+\frac{1}{|S|}\sum_{s\in S}d_s\bar{y}_s$$

  • $\begingroup$ Sorry, I forgot to mention that obviously we only get an upper bound if all subproblems are feasible with the current MP solution $\bar{x}. But very good point to use the primal version of the SP to calculate the upper bound! $\endgroup$ Commented Apr 25 at 14:18

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.