4
$\begingroup$

I've been studying the Benders decomposition method to solve stochastic integer problems.

I've also stumbled across papers using a so called L-shaped-algorithm which also divides into master problem and sub problem.

Are these the same techniques? If not, what are the differences?

$\endgroup$

1 Answer 1

7
$\begingroup$

In the paper that proposed L-shaped method, you can find

In section 2, an algorithm which is essentially the same as the algorithm developed by Benders[3] is described and a geometric interpretation is given.

enter image description here

-- Van Slyke, R. M., & Wets, R. (1969). L-shaped linear programs with applications to optimal control and stochastic programming. SIAM Journal on Applied Mathematics, 17(4), 638–663. https://doi.org/10.1137/0117061

So "Benders decomposition" and "L-shaped method" can be interchangeable.

However, when "L-shaped" is used, one implies the problem is stochastic, as you can find "stochastic programming" in the above title. While Benders decomposition is intended for a more general class of problems.

$\endgroup$
1
  • $\begingroup$ Thank you! Since I'm solely dealing with stochastic problems for now, I can use the methods synonymously. $\endgroup$ Jul 13, 2023 at 14:31

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.