# Two stage stochastic

 1 Hi all, I am working on a two-stage scheduling problem. Written in scenario-based model, it is a large scale problem with continuous first stage variables and mixed integer second stage variables. Due to the nature of my problem, the optimal solution of second stage subproblem can be easily derived when first-stage variables are fixed; and the recourse is relatively complete. Is there any specific algorithm to solve my problem? I read something about benders' decomposition and I think classical benders works for linear case. But my problem has MIP second stage. The reason I did not turn to Integer Benders' is that I try to exploit the special nature of my second stage. But I did not quite know how to generate optimality cuts using second stage optimal solution. Thanks! asked 07 Nov '13, 00:31 PhhhhhhhhhhhhD 21●5 accept rate: 0%

 2 Try to learn berders descomposition, applied to stochastic optimization is call l-shaped method. In gooogle there are a lot of examples http://www.math.uh.edu/~rohop/Spring_12/Chapter1.pdf answered 07 Nov '13, 03:17 Gato_rockero 21●1 accept rate: 0% Thanks, Gato. But I think classical benders works for linear case. But my problem has MIP second stage. The reason I did not turn to Integer Benders' is that I try to exploit the special nature of my second stage. (07 Nov '13, 11:03) PhhhhhhhhhhhhD (07 Nov '13, 16:48) Gato_rockero Thanks again, Gata. I guess I did not make this clear.I did not turn to Integer Benders' like your post is that I try to exploit the special nature of my second stage instead of using a general algorithm I was just wondering if there is a simple way to do generate the cut. The variants of Benders' decompositions I have read assume second stage is NP hard, but mine is not hard to solve. (07 Nov '13, 17:01) PhhhhhhhhhhhhD
 1 Could you give a bit more detail on how the second-stage solution can be easily derived given the first-stage solution? Perhaps it could be formulated as a convex problem that always gives an integer solution (e.g., network flow), in which case standard Benders decomposition could be applied. answered 07 Nov '13, 18:19 Miles 260●3●8 accept rate: 0% Thanks,Miles!The second stage is a scheduling problem, but the constraints are so "tight" that the problem has only one feasible solution and I know exactly what it is as soon as first stage variables are fixed to a set of values. So it is not an "ordinary" optimization problem, but I do have a MIP formulation for it. I can write a program to construct the second-stage solution, but can not write it in closed form. That is the reason why I try to decompose my problem in Benders' or L-shaped method and utilize this special structure. (07 Nov '13, 19:41) PhhhhhhhhhhhhD I am also thinking about the possible connection to Network flow, but I have not figured it out. (07 Nov '13, 19:41) PhhhhhhhhhhhhD
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

×190
×71
×58
×4