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

[Matthew Galati]

Peter - Thank you very much for the reply. I have the 2nd case - so it
seems, I will need to expand my input graph. I saw in the source code that
the graph is already expanded in a similar manner (for detecting
infeasibility). However, this seems to be for the case when all flow balance
constraints are either >= or <=. The mixed case does not seem to be handled.

I will try changing the input graph and let you know if I have any
difficulty.

Thanks,
Matt



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

> Dear All,
>
> Basically, all min cost flow algorithms work with the general inequality
> form of the problem. If you need equalites, you should do the following.
>
>   1. If you need equalites for all nodes, simply ensure that the sum of
> supply values is zero.
>
>   2. If you need equalites for some nodes and inequalities for the
> others, then you should modify (extend) the input graph. Note that this
> use case requires the sum of supply values to be non-positive (typically
> negative, otherwise we have the above case). Let -x denote the sum of
> supply values (x>=0). First, add an extra root node s to that graph with
> supply[s]=x. Then add an arc (s,i) for each node i that needs inequality
> condition. Set the lower bound to 0, the upper bound to x and the cost
> to 0 on these new arcs. Finally, run the algorithm on the new network.
> Now we have sum(supply[i])=0, so we require equalities for all nodes. It
> can be easily verified that the new problem is feasible if and only if
> the original problem is feasible. Moreover, if you restrict an optimal
> solution of the new problem to the arcs of the original graph, then you
> obtain an optimal solution for the original problem.
>
> Regards,
> Peter
>
>
>  > In the documentation for min-cost network flow, it states:
>  > "However if the sum of the supply values is zero, then these two
>  > problems are equivalent. The algorithms
>  > <http://lemon.cs.elte.hu/pub/doc/latest/a00531.html> in LEMON support
>  > the general form, so if you need the equality form, you have to ensure
>  > this additional contraint manually."
>  >
>  > http://lemon.cs.elte.hu/pub/doc/latest/min_cost_flow.html
>  >
>  > What is the best way to do this? Say, you have a set of flow-balance
>  > constraints that are all >=. But, for one node / row, you want to ensure
>  > equality. Let's also assume that sum{ i} supply[i] != 0. That is, the =
>  > and >= are not equivalent. This equality is "another constraint". How do
>  > you go about ensuring this constraint manually? as suggested in the
>  > documentation. Is there any way to adjust the input graph to ensure
>  > this? Or change something in the algorithm to identify one constraint or
>  > the other as = vs >=0?
>  >
>  > Thanks,
>  > Matt
>  >
>  >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20100422/ef6ee659/attachment.html>