Hi all, I am working on a twostage scheduling problem. Written in scenariobased 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 firststage 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 
Try to learn berders descomposition, applied to stochastic optimization is call lshaped method. In gooogle there are a lot of examples answered 07 Nov '13, 03:17 Gato_rockero 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

Could you give a bit more detail on how the secondstage solution can be easily derived given the firststage 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 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 secondstage solution, but can not write it in closed form. That is the reason why I try to decompose my problem in Benders' or Lshaped 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
