[Lemon-user] Network Simplex Initialisation (based on Bonneel's network_simplex_simple.h)
Kovács Péter
kpeter at inf.elte.hu
Wed Jun 3 08:15:59 CEST 2015
Hi,
> 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.
The totalCost() is not to be used for calculating the objective function
value between iterations, only after the algorithm stopped. Note that
the internal network on which the algorithm operates contains so-called
artificial arcs, but they are not included in the calculation of the
totalCost() method. If they were also included, the total cost would not
be 0, but an extremely large cost at the beginning of the algorithm.
> 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)?
There are two types of iterations: (A) replace an artificial arc with a
real one in the spanning tree solution; (B) replace a real arc with
another real one. However, these two types of iterations are not
separated in any way. They are typically performed in mixed order,
although type A iterations are more common at the beginning. Eventually,
all artifical arcs are removed and then a feasible solution is obtained
for the original network. This event could be recognized within the
algorithm (but not in the way you supposed) and the process could be
stopped, but I'm not sure that this result would be practical for any
purpose. (If you are looking for a feasible flow, consider to use the
Circulation class of LEMON.)
Regards,
Péter
>
> 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
>
> _______________________________________________
> 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