Primal Network Simplex algorithm with given starting solution

[Alpar Juttner]

If a primal solution is available, then we don't need the extension of the underlying graphs, which may speed up the algorithm sometimes.

[Peter Kovacs]

Replying to alpar:

If a primal solution is available, then we don't need the extension of the underlying graphs, which may speed up the algorithm sometimes.

Or only a few additional arcs should be introduced (to connect the components of the cycle-free starting solution).

[Alpar Juttner]

Replying to kpeter:

Replying to alpar:

If a primal solution is available, then we don't need the extension of the underlying graphs, which may speed up the algorithm sometimes.

Or only a few additional arcs should be introduced (to connect the components of the cycle-free starting solution).

Or even better: optimize the disconnected blocks separately.

[Peter Kovacs]

Replying to alpar:

Or even better: optimize the disconnected blocks separately.

Not really. Consider the following digraph.

Nodes: {1,2,3,4}
Arcs: {(1,3), (1,4), (2,3), (2,4)}
Costs: c(1,3) = c(2,4) = 20, c(1,4) = c(2,3) = 10
with unifrom 1 capacities and 1 supply at nodes 1 and 2, 1 demand at nodes 3 and 4.

If the starting solution consist of arcs (1,3) and (2,4) with 1 flow value on both arcs, then optimizing these parts separately won't result in a minimum cost flow.

The only case when the problem could be decomposed easily is when the underlying graph is not weakly connected. Then weakly connceted components can be optimized separately.

NS needs a spanning tree that contains all the free arcs. After eliminating all the free cycles from the starting solution, we have a forest consisting of the free arcs. Suppose the digraph is weakly connected. Then we have to connect these trees into one spanning tree. It could be done with selecting some of the non-free arcs, but it is more difficult and possibly less efficient than adding one extra root node and a few arcs connecting each tree of free arcs to this root node.

(I call an arc "free" if its flow value is greater than the lower bound and less than the upper bound. A free cycle is an undirected cycle consisting of free arcs.)

[Alpar Juttner]

Replying to kpeter:

Replying to alpar:

Or even better: optimize the disconnected blocks separately.

Not really.

I still keep on believing that.

Consider the following digraph.

Nodes: {1,2,3,4}
Arcs: {(1,3), (1,4), (2,3), (2,4)}
Costs: c(1,3) = c(2,4) = 20, c(1,4) = c(2,3) = 10
with unifrom 1 capacities and 1 supply at nodes 1 and 2, 1 demand at nodes 3 and 4.

This example is connected, thus the basic solutions correspond to spanning trees.

If the starting solution consist of arcs (1,3) and (2,4) with 1 flow value on both arcs, then optimizing these parts separately won't result in a minimum cost flow.

This example is connected. You can of course decompose only if the graph is not connected.

The only case when the problem could be decomposed easily is when the underlying graph is not weakly connected. Then weakly connceted components can be optimized separately.

NS needs a spanning tree that contains all the free arcs.

Let us call it "basis".

After eliminating all the free cycles from the starting solution, we have a forest consisting of the free arcs. Suppose the digraph is weakly connected. Then we have to connect these trees into one spanning tree. It could be done with selecting some of the non-free arcs, but it is more difficult and possibly less efficient than adding one extra root node and a few arcs connecting each tree of free arcs to this root node.

It is certainly no less efficient as you have to do it only once. Depending on how you implement the eliminations of free cycles, the full tree of the basis is

• either already in your hand at the end of the process (in case you used a BFS/DFS for detecting the cycles)
• or it can be obtained very efficiently by doing some additional steps (in case you applied a Kruskal type approach).

Note, that #216 already suggests that the algorithm eliminating the free cycles should also provide the basic tree.

[Peter Kovacs]

Replying to alpar:

This example is connected, thus the basic solutions correspond to spanning trees.

Yes. The only question is how you extend the forest of free arcs to result in a tree. I just want to show you that the components that is induced by the trees of the forest usually cannot be optimized separately.

It is certainly no less efficient as you have to do it only once. Depending on how you implement the eliminations of free cycles, the full tree of the basis is

• either already in your hand at the end of the process (in case you used a BFS/DFS for detecting the cycles)

First you have to consider the subgraph of free arcs and after a DFS is finished but not all nodes have been visited, you have to select a non-free arc that is incident to a visited node. So you have to search the nodes again or you have to store at each node the first incident non-free arc. You are right, it is not a big deal, but maybe it is not better than introducing a new arc for each tree. Maybe you get a spanning tree with less depth with new arcs, so the pivots could be faster.

I think both solutions should be tested.

[Alpar Juttner]

First you have to consider the subgraph of free arcs and after a DFS is finished but not all nodes have been visited, you have to select a non-free arc that is incident to a visited node. So you have to search the nodes again or you have to store at each node the first incident non-free arc.

There are better ways to do it.