[Lemon-user] equality form of min-cost network flow
Kovács Péter
kpeter at inf.elte.hu
Tue Aug 3 22:55:32 CEST 2010
Dear Matt,
For simplicity, I answer your three email at once.
> 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.
That's absolutely right.
> 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?
Currently, the mixed inequality nodes are considered as special GEQ
nodes. A GEQ node has an incomming arc from the root node which covers
the "extra supply" of the node (i.e. OUT(u)-IN(u)-suppyly[u]). If this
node also has a LEQ contraint, then this incomming arc has a finite
capacity supply_up[u]-supply[u]. (The actual implementation is more
difficult because of the cost issues, but this is the main idea.)
> For the new code you sent that allows for <= constraints. In the
> section where you adjust for nonzero lower bounds on arcs
> (_have_lower), you only adjust the _supply. Don't you have to adjust
> _supply_up as well?
That's a real mistake indeed, I've just forgotten it. Thank you for the
warning. I attached a fixed code to this mail and also to the ticket
#375. Consider to use this one. (I also modified the test file to check
this aspect case as well.)
Actually, this bug caused the faulty results of the code you sent in
your third email. Using the new version, it is almost good. Another
problem is the usage of too large INF constant, which cause precision
problems. If you use e.g. 1e+10, then the program prints out the correct
result (15.3478). Using larger constants (e.g. 1e+14 or 1e+15) results
in similar, but not precise solution.
I hope, I could help you.
Best regards,
Peter
> 2010/7/28 Kovács Péter <kpeter at inf.elte.hu <mailto: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> <mailto: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 embedded and charset-unspecified text was scrubbed...
Name: network_simplex.h
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20100803/5a9b5c84/attachment.h>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: min_cost_flow_test.cc
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20100803/5a9b5c84/attachment.ksh>
More information about the Lemon-user
mailing list