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's gravatar image

PhhhhhhhhhhhhD
215
accept rate: 0%

edited 07 Nov '13, 11:04


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

link

answered 07 Nov '13, 03:17

Gato_rockero's gravatar image

Gato_rockero
211
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

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 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.

link

answered 07 Nov '13, 18:19

Miles's gravatar image

Miles
26028
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
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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

Asked: 07 Nov '13, 00:31

Seen: 1,015 times

Last updated: 08 Nov '13, 04:31

OR-Exchange! Your site for questions, answers, and announcements about operations research.