# How can I calculate the UB if I'm using Fischetti's Alternative Cut Generation for Benders'?

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?

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$$