Optimality in L Shaped or Bender Decomposition

Question

I was working on solving a two-stage stochastic problem using L Shaped method (Benders Decomposition). I have discussed the model here: Stochastic Facility Location Model.

Do the single-cut/ multi-cut methods guarantee optimality? Is there any way to prove this?

Answer 1

As far as I can see you have binary variables in the first stage and general integer variables in the second stage. This means that classical Benders cuts (based on duality of the subproblems) do not ensure convergence.

Conversely, convergence is ensured by combinatorial cuts generated as follows. Let

• $Q(y)$ be the recourse function -- the expected second-stage cost -- for a given first-stage (master problem) solution
• $L$ be a valid lower bound to $Q(y)$, i.e., $L \leq \min_yQ(y)$
• $\theta$ be the variable which approximates $Q(y)$ in the master problem
• $y^n$ be the solution to MP at iteration number $n$
• $I^n$ be the set of the indices of $y^n$ where $y$ takes value $1$, i.e., the indices of the open facilities in your specific case.

The following optimality cuts ensure convergence $$\theta\geq (Q(y^n)-L)(\sum_{i\in I^n}y_i^n-\sum_{i\notin I^n}y_i^n )- (Q(y^n)-L)(|I^n|-1)+L$$

This unfriendly-looking expression does precisely one thing: binds exactly the value of $\theta$ to $Q(y^n)$ when MP generates $y^n$, and yields a generally valid (possibly weak) lower bound elsewhere. You can check yourself that, for $y=y^n$ it reduces to $$\theta\geq Q(y^n)$$ and for $y\neq y^n$ it reduces to $$\theta \geq L - \text{a positive constant}$$ You will find a more thorough explanation in this article which introduced them.

They also provide a proof of convergence. In a nutshell, the argument is the following: Since the first-stage decisions are binary, there will be a finite number of first-stage solutions and thus, with a finite number of cuts, you will be able to bind the value of $Q(y)$ for all $y$ exactly.

Finally, as I briefly said above, ordinary L-Shaped duality-based cuts do not ensure convergence. Such cuts will only provide a lower bound to $Q(y)$ but will not be able to cut off $(y^n,\theta^n)$ solutions for which $\theta^n<Q(y^n)$. This is also proven in the article above, but the argument is the following: if you solve the LP relaxation of your second-stage problem, you end up with a lower bound to $Q(y)$, which is the expectation of the optimal solution to your integer programs.