[Lemon-user] equality form of min-cost network flow

[Matthew Galati]

In the mixed inequality case, I am trying to understand what the augmented
graph is doing at with the _root node. Normally, it seems that this node
will have -1 * the sum of the supply/demand of the original graph.
Therefore, bringing everything into equality form with sum of supply/demand
= 0. However, in the case where we have some <= and >= constraints, are we
suppose to still use -sum_supply? What about _supply_up[root] - should that
be set to something? Is the "constraint" associated with the _root node
meant to be an >= or = type constraint? To have a fully balanced flow in the
augmented graph, should we be adding the supply[u] for >= and supply_up[u]
for <= nodes?

Thanks,
Matt





2010/7/28 Kovács Péter <kpeter at inf.elte.hu>

> Dear Matt,
>
> I see your problem, a more general support could be implemented to NS.
> Unfortunatelly, I don't have enough time to do it at the moment, but I will
> try to find some time for that.
>
> With the current solution, you should consider a certain finite value as
> infinite. E.g. using 'long long int' value type, numeric_limits<long long
> int>::max()/number_of_nodes could be a good choice, it wouldn't cause
> overflow problems inside NS.
>
> Regards,
> Peter
>
>
> 2010.07.27. 22:15 keltezéssel, Matthew Galati írta:
>
>> I have an interesting case that I am not sure how to handle with the
>> current solver.
>>
>> It is a graph with one arc and 2 nodes. The arc goes from node 1 to 0.
>> Both nodes have supply=0, but one is a >= and one is a <=.
>>
>> That is,
>>
>> supply_lb[0] = -infinity
>> supply_ub[0] = 0
>>
>> supply_lb[1] = 0
>> supply_ub[1] = infinity
>>
>> The arc(1-0) has no capacity (infinite) and cost=58.0.
>>
>> So, I have no way to easily bound supply_lb[0] to a finite value.
>>
>> How can I handle this case?
>>
>> Thanks,
>> Matt
>>
>>
>> 2010/7/20 Kovács Péter <kpeter at inf.elte.hu <mailto:kpeter at inf.elte.hu>>
>>
>>
>>    Dear Matt,
>>
>>    "Infinite" means std::numeric_limits<Number>::max() or
>>    std::numeric_limits<Numer>::infinity() (if it exists). You can use
>>    any "small enough" negative finite value. Such a value could be
>>    found relatively easily in most cases. E.g. the negative of the sum
>>    of all arc capacities is surely suitable, if it does not cause
>>    overflow problems. Otherwise you can use another value or a larger
>>    number type (e.g. long long int or double).
>>
>>    Of course, a better support could be impleneted that correctly
>>    handles negative infinite bounds, but the current solution is based
>>    on the GEQ formulation, so it requires finite lower bounds.
>>
>>    Regards,
>>    Peter
>>
>>    2010.07.20. 14:44 keltezéssel, Matthew Galati írta:
>>
>>        Hi Again,
>>
>>        It states in the ticket that infinite lower bounds are not
>>        supported for
>>        supply nodes. Does this mean that LEQ constraints are not
>>        supported? Is
>>        there any workaround for this? I currently have examples where I
>>        have
>>        both LEQ,GEQ and EQ constraints. I cannot just "flip" the LEQ to
>>        GEQ,
>>        because this would break the network structure (+1/-1). Any
>>        workarounds?
>>
>>        Since LEQ-GEQ constraints are allowed (when both are finite) -
>>        is there
>>        some "big enough" finite value for the supply lower bound than
>>        can be
>>        used to represent infinity and have it still work?
>>
>>        Thanks,
>>        Matt
>>
>>        However, I made a working solution for the lower-upper bound
>>        formulation. I attached a patch to the corresponding ticket:
>>
>>        http://lemon.cs.elte.hu/trac/lemon/ticket/375
>>        I also attached the modified files to this letter for the sake
>>        of simplicity.
>>
>>        This version of NS can solve your problem with GEQ and EQ supply
>>        constraints. For a GEQ node, you should use sufficiently large
>>        (or infinite) upper bound and for an EQ node, you should use the
>>        same value for lower and upper bound.
>>
>>        I hope this solution helps you in your work.
>>
>>        Best regards,
>>        Peter
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20100802/30066f42/attachment.html>