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

[Kovács Péter]

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