Hi,

I am trying to understand column generation algorithms for LP. How is it different from Revised Simplex?
Whats the connection with Dantzig-Wolfe decomposition?

thanks

asked 09 Apr '15, 10:10

cbot's gravatar image

cbot
558
accept rate: 0%


Hi @cbot, column generation is the revised simplex method with a particular pricing rule: instead of explicitly checking all non-basic variables for negative reduced cost (assuming a minimization problem here), you solve an auxiliary optimization problem to see whether such a variable exists (and if so, which one it is). This pricing problem is another LP, essentially minimizing the reduced cost subject to "the structure how coefficient vectors of variables look like." The relation to Dantzig-Wolfe is that the form of this auxiliary problem comes very naturally out of DW decomposition. It happens that I wrote a lot about the topic, see e.g. here. Shoot if you have more concrete questions --Marco

link

answered 09 Apr '15, 10:20

Marco%20Luebbecke's gravatar image

Marco Luebbecke ♦
3.4k1615
accept rate: 16%

Marco, what would the sub problem look like for a TSP problem? Would it be a knapsack? Number of total edges in asymmetric TSP is huge, but the solution is guaranteed to only use n-1 of them, so it seems like a candidate for column generation. But, I can't seem to find examples of column generation for anything but cutting stock

I understand that branch and price does this in a way during each step. My concern there is that branch and price would run slower, and I would like to have more control over which columns enter the problem and have the option to save these columns in my database for future solves to be added from the get-go.

link

answered 13 Sep '17, 09:47

gtg489p's gravatar image

gtg489p
3314
accept rate: 0%

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:

×231

Asked: 09 Apr '15, 10:10

Seen: 925 times

Last updated: 13 Sep '17, 09:47

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