# Infinite loop in column generation algortihm

I have to program the following:

Input:

• I have k commodities that have to go from place i to j with a certain demand
• There are n nodes and the cost for traveling one piece between the nodes i and j
• Each arc has a given maximal capacity

The assignment is to find the best flows to fulfill all demand, minimizing the cost.

I have to use column generation, so first I do a phase 1 simplex, to find a feasible set of paths to use before I can start the optimization process.

Therefore these are the steps I take:

1. I add the weight z to all capacities
2. The master problem: Use simplex to solve the problem given the initial paths, trying to minimize z
3. If the sum of the z's is zero, the original problem is feasible, go on with phase2 simplex. If not, go to step 4
4. The sub problem generates k new paths (a path for each commodity) to add to the initial set. It tries to maximize the dual variables corresponding to the z's.
5. Repeat steps 2-4 until a feasible set of paths is found.

However, my sub-problem generates after some iterations only paths that are already known.

I wrote the sub-problem using Dijkstra instead of a simplex formulation.

I can find no reason why my sub-problem does not generate new paths. I thought about several things that might be the problem:

• I use n*n z's, instead of only one. But in theory also one z could do the task. But then, how should I handle the dual variables in the sub-problem?
• In class we only used a simplex formulation of a sub-problem. I thought that if a sub-problem is a shortest-path problem I can also use a shortest-path formulation.

However, I am more guessing than arriving at good educated ideas about the mistake in my program. What might be the reasons why my sub-problem generates only already existing paths in my code?