1
$\begingroup$

I am currently trying to understand the integer L-shaped-method/stochastic version of Benders Decomposition because I have practical problem MIP that is stochastic and thus has very good decomposition structure for Benders.

To get familiar with Benders Decomposition, I started off with implementing the deterministic version of my problem with Benders. That worked successfully and I'd like to think I understood the Benders algorithm in the deterministic case with integer variables in the master problem and continuous variables in the subproblem.

Now though, I kind of struggle to transform my problem into a stochastic enviroment. The main issue is that I can't seem to find good material/literature that explain this step going from deterministic Benders to the stochastic version.

Most literature explains the L-shaped-method in a very theoretical manner (i.e. Van Slyke and Wets 1969, Kall and Wallace 1994, Birge and Louveaux (2011). I struggle to follow the explanations given in those works. Mainly because it seems so far away from the original Benders without explaining in detail where the differences come from. Also, I think for the most part these works concentrate on LPs and not on MIPs.

With this post, I wanted to ask if anyone knows good material that is more "hands-on" and delivers a more practical approach (maybe even an example) for the integer L-shaped-method/stochastic integer Benders?

Maybe, if one is familiar with the method, he could even explain it himself.

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
0
$\begingroup$

The "integer L-shaped method" and the "stochastic version of Benders Decomposition" are not the same thing. To understand the "integer L-shaped method" you need to first understand the relationship between the "Benders Decomposition" and the "L-shaped method / stochastic version of Benders Decomposition"; then the relationship between the "L-shaped method" and the "integer L-shaped method", as follows:

Benders -> (uncartainty) -> L-shaped -> (integer sub problem) -> integer L-shaped

  1. The Benders Decomposition tackles one sub problem in each iteration, while the sub problem of the L-shaped method is a set of sub problems, one for each scenario. For understanding "Benders -> L-shaped", I recommend:

  2. The Benders Decomposition and the L-shaped method relies on the dual of the sub problem(s) to generate Benders cuts. Thus, the sub problem(s) must be pure linear programming without integer variables. The integer L-shaped method differs from the previous two because it allows binary (0-1) varialbes in the subproblems. The main difference between the L-shaped and integer L-shaped is the form of the Benders cut. For understanding "L-shaped -> integer L-shaped", I recommend:

    • [the original work] Laporte, G., & Louveaux, F. V. (1993). The integer L-shaped method for stochastic integer programs with complete recourse. Operations Research Letters, 13(3), 133–142. https://doi.org/10.1016/0167-6377(93)90002-X
    • [a more recnet enhancement] Angulo, G., Ahmed, S., & Dey, S. S. (2016). Improving the integer L-shaped method. INFORMS Journal on Computing, 28(3), 483–499. https://doi.org/10.1287/ijoc.2016.0695
Improve this answer
$\endgroup$
2
  • $\begingroup$ Wow, thank you for that great write up! I'll look into the material you posted. So the first thing I learned now, I don't need the integer L-shaped-method since I only have continuous variables in my second stage. So just for clarification, the difference between Benders and L-shaped lies in the fact that for Benders, we continue to have only one subproblem, even if we have i.e. 100 scenarios, while in the L-shaped method we have a subproblem for each scenario meaning 100 subproblems in that case? $\endgroup$
    – Arctic_Skill
    Commented Oct 27, 2023 at 7:01
  • $\begingroup$ Also the link to the slides to that video from J. Luedtke is dead, do you know if I can find them somewhere by any chance? I quick google search with the lecture name didn't yield any results. $\endgroup$
    – Arctic_Skill
    Commented Oct 27, 2023 at 7:04
0
$\begingroup$

My personal experience to learn L-shaped method, I used "Introduction to Stochastic Programming" by John R. Birge

Also, I tried to implement Integer L-shaped method in C# and Cplex by referencing "Laporte, G., & Louveaux, F. V. (1993). The integer L-shaped method for stochastic integer programs with complete recourse. Operations research letters, 13(3), 133-142." You can refer my github, I have uploaded my source code https://github.com/ytsao/Integer-L-shaped-method/blob/main/IntegerLShapedMethod-Final/IntegerLShapedMethod/ILShaped.cs

In addition, my friend's research is related Integer L-shaped method as well. "Lin, D. Y., & Kuo, J. K. (2021). The vehicle deployment and relocation problem for electric vehicle sharing systems considering demand and parking space stochasticity. Transportation Research Part E: Logistics and Transportation Review, 156, 102514."

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Thank you very much for those suggestions! I program in C++ but I'll certainly take a look into your code. $\endgroup$
    – Arctic_Skill
    Commented Oct 27, 2023 at 7:17
  • 1
    $\begingroup$ additional source code, you can refer this repository, but that using python instead of C++. github.com/RahmanKhorramfar91/… $\endgroup$
    – ytsao
    Commented Oct 27, 2023 at 9:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.