[Lemon-user] Network Simplex Initialisation (based on Bonneel's network_simplex_simple.h)
Kovács Péter
kpeter at inf.elte.hu
Fri Jun 5 23:22:14 CEST 2015
Hi Matthew,
> Hi,
>
> Thank you again!
>
> I actually do have another question.
>
> I am lacking a bit of intuition regarding this algorithm and I was
> hoping you could help me.
>
> So, in the NS algorithm, if for a given pivot, we have delta == 0, then
> we call this pivot degenerate, the flow cost is not reduced and we just
> modify the spanning tree.
>
> On the few experiments I have done, I get a majority of degenerate
> pivots thus the difference between the performance with the normal LEMON
> initialization and the performance with the initialisation as discussed
> before with the optimal solution as initial solution is not significant.
> I, of course, get no non-degenerate pivots when I give an initial
> solution that is optimal.
>
> So I would like to know : in general, does the NS algorithm generate a
> majority of non-degenerate pivots? (am I getting an anomaly?)
No, not necessarily. Experiments with certain classes of large-scale
min-cost flow problems showed that more than 90% of the pivots may be
degenerate.
> And, if we use the previously discussed initialisation, does the
> distance between the initial solution and the optimal solution have a
> significant impact on the overall performance of the algorithm? (i.e. if
> I initialise with a good enough initial solution, do you think it would
> go much faster than a normal initialisation?)
I haven't made such experiments and the properties of the problem
instance can also be crucial. I mean, if the algorithm can solve the
problem easily from scratch (with relatively few number of pivots), then
starting from a near optimal solution will not make it much faster.
On the other hand, if you think that the initial flows are really very
close to optimal, you can give a try to the CycleCanceling algorithm. In
general, it is much slower than network simplex in solving problems from
scratch, but it may be practical if your flow is "almost" optimal.
However, I have never experimented with such use cases.
Best regards,
Péter
> All the best,
>
> Matthew
>
> On Tue, Jun 2, 2015 at 10:12 PM, Kovács Péter <kpeter at inf.elte.hu
> <mailto:kpeter at inf.elte.hu>> wrote:
>
> Hi Matthew,
>
> I'm glad to hear that the solution works for you.
>
> Should you have any further question, feel free to contact me or the
> lemon-user mailing list.
>
> Regards,
> Péter
>
>
> Hi Peter,
>
> I got the code to work! Thank you very much for your time, it is
> much
> appreciated.
>
> The algorithm does indeed work as-is, I had a problem with my arc
> numbering...
>
> I shall learn to be more cautious when modifying other people's
> code. :)
>
> If my project is successful, I'll let you know.
>
> Thanks again,
> All the best,
>
> Matthew Henry
>
> On Sat, May 30, 2015 at 7:32 AM, Kovács Péter
> <kpeter at inf.elte.hu <mailto:kpeter at inf.elte.hu>
> <mailto:kpeter at inf.elte.hu <mailto:kpeter at inf.elte.hu>>> wrote:
>
> 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
>
>
>
>
More information about the Lemon-user
mailing list