[Lemon-user] Network Simplex Initialisation (based on Bonneel's network_simplex_simple.h)

[Kovács Péter]

Hi Matthew,

> Hello!
>
> Thank you very much for your fast and detailed answer, it is much
> appreciated.
>
> /"Anyway, why is it important for you to start the algorithm with
> initial flow values? Merely for efficiency reasons? Maybe the algorithm
> is efficient enough without such guidance. Have you tried it?"/
>
> Well, I would like to develop a multi-scale algorithm, so the input on
> one scale would depend on the optimal flow of the previous scale, and
> that input would hopefully be quite close to the optimal flow on the
> current scale, hence the need to be able to initialise the algorithm at
> given flow values.

I see. Currently, the min-cost flow implementations in LEMON do not 
provide direct support for this, but the transformation I wrote should work.

> /
> "You can transform the input of the algorithm, rather than the algorithm
> itself, which is an easier and safer way. For each arc e=(i,j) having
> d=initialValues_[i][j] > 0,
>    * decrease the capacity of e with d
>    * add a reverse arc e'=(j,i) to the graph with capacity d and cost
> equal to -cost[i][j]
> Furthermore (assuming that the initial flow was feasible), set the
> supply/demand values to zero for each node.
>
> If you find an optimal flow x in this modified graph and sum it with
> your initial flow, then you will get an optimal flow in the original
> graph. (The flow value for an arc e in the original graph should be set
> to initialValue[e] + x[e] - x[e'].)"/
>
> This approach looks a lot simpler and safer. And I am trying to
> implement it, however it just returns optimal and all arcs have zero
> flow in the modified graph, even though the initial flow on the original
> graph is not optimal.

Are you sure? I have tested it with a simple example and it works. See 
the attached DIMACS files. This is a standard format for describing 
min-cost flow problem instances, its definition can be found here: 
http://lpsolve.sourceforge.net/5.5/DIMACS_mcf.htm

The example.dim file describes the first input. The optimal flow 
delivers 10 units of flow along the path 1->2->3, 15 units along the 
path 1->4->5, and 5 units along the path 1->2->4->5. If you apply the 
suggested transformation before changing the original graph (i.e. the 
residual network is created with respect to the optimal flow), you will 
get example_residual.dim. In this instance, the optimal flow is the 
constant zero flow, which validates the optimality of the considered 
flow. (Actually, the arcs with 0 capacity could be removed, but I kept 
them for easier understanding.)

After that, let's suppose that the cost of the 2->4 arc of the original 
network is decreased from 1000 to 600. Then our flow is no longer 
optimal. The transformation yields the network described in 
example_residual_modified.dim. And if you run network simplex (or any 
other algorithm) on this input, it will find a flow of total cost -1000, 
which delivers 10 units of flow along the residual cycle 4->1, 1->2, 
2->4. The total cost of the cycle is -1500 + 800 + 600 = -100, hence an 
optimal flow will saturate this.

Let's sum this new flow and the original one. 4->1 in the new flow is a 
reverse arc, so the original flow value should be decreased on the 
corresponding arc 1->4 with 10 units. The other two arcs are original, 
so the corresponding flow values should be increased with 10 units. 
Thus, the resulting composed flow delivers: 10 units along the path 
1->2->3, 5 units (instead of 15) along the path 1->4->5, and
15 units (instead of 5) along the path 1->2->4->5. Which is indeed 
optimal with respect to the modified costs.

I hope this example makes the transformation clear.


> I have noticed that in the initialisation, since the supply/demand
> values on all my nodes is zero, all the artificial arcs go from the
> nodes to the root with zero flow.

That's right.

> And, I suppose, the 1st thing the algorithm wants to do is pass flow
> through the arcs with negative cost (if my initial flow is not optimal).
> But it can't do that since that would mean that one of the artificial
> arcs would have to have negative flow. Thus the algorithm stays with no
> flow on all arcs.

Well, the behavior of network simplex algorithm is a bit more complex. 
You are right that it cannot send flow along the negative arcs in the 
first iteration(s). However, the algorithm won't stop there. It will 
change the tree (by adding a negative arc and removing an artifical arc) 
and will go along. After a few such degenerate iterations, it will reach 
a state when it eventually can send positive amount of flow along a 
cycle consisting of non-artifical arcs with negative total cost. But 
this can happen only after all but one arcs of this cycle have been 
added to the spanning tree.

In fact, if the algorithm is run on example_residual_modified.dim, then 
5 iterations are perfromed with delta values: 0, 0, 0, 0, 10.

> I have tried setting the artificial arcs from sink nodes to the root in
> the reverse direction (i.e. from root to sink node) and setting their
> capacity to the maximum flow they would have in the algorithm (i.e.
> demand value of sink node in original graph), so that flow can pass
> through them and so that they are able to leave the current spanning
> tree. But it does not seem to work.

Don't do this. The algorithm, including the initialization phase, is 
correct, though not trivial. :)

> Am I interpreting this correctly? Do you see why I have a problem? Is
> there an easy strategy?
>
> Thanks again,
>
> Matthew Henry


Best regards,
Péter
-------------- next part --------------
p min 5 5
n 1 +30
n 3 -10
n 5 -20
a 1 2 0 30  800
a 1 4 0 15 1500
a 2 3 0 10  200
a 2 4 0 15 1000
a 4 5 0 20  500
-------------- next part --------------
p min 5 5
a 1 2 0 15   800
a 2 1 0 15  -800
a 1 4 0  0  1500
a 4 1 0 15 -1500
a 2 3 0  0   200
a 3 2 0 10  -200
a 2 4 0 10  1000
a 4 2 0  5 -1000
a 4 5 0  0   500
a 5 4 0 20  -500
-------------- next part --------------
p min 5 5
a 1 2 0 15   800
a 2 1 0 15  -800
a 1 4 0  0  1500
a 4 1 0 15 -1500
a 2 3 0  0   200
a 3 2 0 10  -200
a 2 4 0 10   600
a 4 2 0  5  -600
a 4 5 0  0   500
a 5 4 0 20  -500