Hi, I am trying to understand column generation algorithms for LP. How is it different from Revised Simplex? thanks
asked
cbot |

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
Marco Luebbecke ♦ |

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