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

[Kovács Péter]

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
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>