From my textbook, I learned bender's decomposition for 2-stage problems and the y variables is non-overlapping. Indeed, I wish to look into this decomposition further since it is very likely a solution to two of my difficult LPs:

https://www.or-exchange.org/questions/10340/method-of-separation-for-lps-with-exponentially-many-constraints https://www.or-exchange.org/questions/10401/simultaneous-column-and-row-generation-reference

but from the textbook, its structural is not exactly what my problem is since its y-variable is not overlapping:

alt text

To address my problem, I hope that there is a version of bender's decomposition with overlapping y variables. Do you have some recommendation (books) that I could look into? Thank you:)

asked 18 Oct '14, 13:59

Chivalry's gravatar image

accept rate: 0%

Are your \(x\) variables integer-valued? If not, I'm not sure why you would want to use Benders, which is designed for master problems that are MILPs (or, I think, NLPs).

If your mission is just to decompose a large LP into smaller LPs, you might want to look into Dantzig-Wolfe decomposition. If the number of "overlapping" variables between any two blocks is relatively small, you might try the following trick. Suppose that \(y_k\) belongs to two blocks. Create a clone \(y_{k}'\), substitute \(y_{k}'\) for \(y_k\) in one block but not the other, and add a constraint \(y_k = y_{k}'\) to the master problem.


answered 18 Oct '14, 14:51

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
accept rate: 19%

Thank you very much for hinting me on that... I would try that :)

(18 Oct '14, 16:16) Chivalry
Your answer
toggle preview

Follow this question

By Email:

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



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



Asked: 18 Oct '14, 13:59

Seen: 6,334 times

Last updated: 18 Oct '14, 16:16

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