[Lemon-user] Network Simplex Initialisation (based on Bonneel's network_simplex_simple.h)
Jean Bertrand Gauthier
jean-bertrand.gauthier at hec.ca
Tue Jun 2 22:46:30 CEST 2015
Can I go back to one your first explanations?
""
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.
""
When I output the totalCost() after every iteration, the first
iterations go from 0 to some values and then the objective function goes
back down eventually reaching the optimal minimal solution.
Is this equivalent to a Phase I simplex? I do not see the separation
betwen these operations. Would it be possible to stop the algo after an
initial solution (i am guessing the one just before it goes down)?
Thank you.
On 2015-06-02 4:12 PM, Kovács Péter 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>> 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
>>
>>
>
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
More information about the Lemon-user
mailing list