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

<br>I will try changing the input graph and let you know if I have any difficulty.<br><br>Thanks,<br>Matt<br><br><br><br><div class="gmail_quote">2010/4/22 Kovács Péter <span dir="ltr"><<a href="mailto:kpeter@inf.elte.hu">kpeter@inf.elte.hu</a>></span><br>

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