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!