5
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks for the detail explanation. What happens when only the first stage variable is integer, and the second stage variables are continuous? $\endgroup$
    – mars
    Dec 7 '21 at 22:07
  • 1
    $\begingroup$ In that case duality still holds for the subproblems and classical Benders cuts ensure convergence. Since the first-stage variables are integer you might be better off by embedding Benders decomposition into a Branch and Bound framework. But that only affect efficiency, the method converges regardless. $\endgroup$
    – k88074
    Dec 8 '21 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.