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:
- I add the weight z to all capacities
- The master problem: Use simplex to solve the problem given the initial paths, trying to minimize z
- 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
- 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.
- 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?