# Column generation algorithm gets stuck — subproblem returns an existing column in master

I have implemented a column generation algorithm to (try to) solve a computationally large transportation routing problem. The gist of the algorithm is the classic column generation scheme: 1) start with a feasible (but non-optimal) set of columns in the master problem. 2) Solve master problem and get the dual values. 3) Create a subproblem and apply the reduced costs from the dual values of the master problem. 4) Solve the subproblem, which produces a new column. 5) Add the new column to the master problem, and repeat steps 2-5 until no column with a reduced cost is found.

The problem I have, is that for datasets over a certain size, there comes an iteration of the suproblem that produces a column that already exists in the master problem. So, the algorithm is basically stuck there. The master problem produces the same result (and dual values), and the subproblem produces the same column, and there is no convergence from that point forward. The solution at that point is not optimal, and the master basis is not improving.

I would like to know, has anyone dealt with this issue of column generation master/subproblem iterations where the subproblem produces an already present column? Is there a way to deal with that, or does it indicate some logic error in my algorithm?

Do you have any suggestions for how to debug why this situation occurs?

With smaller data sets, it doesn't happen, which is puzzling to me. I guess there is a logic error that only becomes apparent on large data sets.

If you can help me navigate this convoluted maze of column generation, I will be forever grateful!

-

I would say you have a logic error in your algorithm. The reason is that when you obtain the optimal solution for the current master problem, each column that is currently in the master problem must have a positive or zero reduced cost (as this is the condition for optimality). However, the column output by the subproblem must have a negative reduced cost, as it corresponds to an entering variable in the simplex method (every entering variable must have a negative reduced cost). So the column generation algorithm shouldn't be producing a column that's already in the master problem. Since the reduced cost calculation is in the objective of the subproblem, that would be a good place to start looking for the logic error.

-
Thank you Mike, the logic error was a discrepancy column pricing in master and the subproblem. Your comment helped me sniff it out. Thanks a ton. – thedudeabides Oct 5 '11 at 2:15
I'm on to next challenge, which is the master LP is actually a LP relaxation of an IP, and the result values found in the optimal soln of the master LP are fractional. Any tricks you know of to steer the column generation model towards integer values in the solution of the master problem? Initially, I naively put an integer restriction on the master problem. But that seems to mess with the dual values during column generation. – thedudeabides Oct 5 '11 at 3:03
@thedudeabides: Yes, it would; dual variables with IPs don't play as nicely as their LP cousins. One of the more successful approaches for tackling IPs when using column generation goes by the name "branch and price." Try searching on that, and see if that helps. – Mike Spivey Oct 5 '11 at 3:17