I have to program the following:


  • 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?



You must log in to answer this question.

Browse other questions tagged .