# column generation algorithm

 2 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 55●9 accept rate: 0%

 5 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 answered 09 Apr '15, 10:20 Marco Luebbecke ♦ 3.4k●1●6●15 accept rate: 16%
 0 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. answered 13 Sep '17, 09:47 gtg489p 33●1●4 accept rate: 0%
 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: