Hi. I would be very interested in using such extensions. Has this been implemented yet? Or, are there any plans to implement this?<br><br>Thanks,<br>Matt<br><br><br><br><br><br><br><div class="gmail_quote">2010/4/30 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="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">Dear All,<br>
<br>
In short, we could implement the following extensions without serious difficulties and without running time overhead:<br>
<br>
* m_l<=Ax<=m_u support for NetworkSimplex, even for negative or positive "infinite" values in m_l and m_u, respectively. This version is a common generalization of all other forms.<br>
<br>
* m_l<=Ax<=m_u support for the other MCF solvers if all values in m_l is finite (upper bounds could be infinite).<br>
<br>
<br>
In details:<br>
<br>
The general m_l<=Ax<=m_u form can be transformed to the Ax=m form by adding a new node and several arcs to the graph (they represent the slack variables of the constraints). Basically, all min cost flow algorithms solve this equality form and any other form should be transformed to this one. Therefore, all implementations could be generalized to the m_l<=Ax<=m_u form, though it could cause some technical difficulties if we allow "infinite" values for these bounds. The major problem here is that the MCF algorithms copies the graph into an internal storage (with the required artifical node and arcs) _before_ they get the maps. (The reason for that is the support of rerunning the algorithm with modified map values but without copying the graph again.)<br>
<br>
Currently, the MCF algorithms support the m_l<=Ax form. They all could be simply extended with support of the m_l<=Ax<=m_u form if all values in m_l remains finite (upper bounds could be infinite), since only the capacities of the artifical arcs should be modified. However, supporting negative infinity as lower bound would cause more difficulties, since it would require the modification or extension of the internal graph representation, which cannot be ensured without running time overhead, because the arcs are stored in a sorted order.<br>
<br>
NetworkSimplex is a different case, since it uses a simpler internal graph representation, which does not require a specific order of the arcs. So the stack-like arc addition and deletion in the corresponding vectors can be performed efficiently.<br>
<br>
Btw., would we like to support the case when both bounds are infinite? This would be more difficult and somewhat slower, because it requires two artifical arcs instead of one.<br>
<br>
Another important question here is the compatible and nice extension of the current interface. NetworkSimplex has supplyMap(map) and supplyType(type) functions (where type can be LEQ or GEQ). They can be used to specify the Ax<=m or the Ax>=m forms. Should we add a new function supplyBounds(m_l, m_u) that would override the effect of both above functions? Wouldn't it be confusing?<br>
<br>
I think, it would be better to combine supplyMap(map) and supplyType(type) into a supplyMap(map, type=GEQ) function and make supplyType() deprecated. (Other MCF classes don't have such a function.)<br>
<br>
<br>
Moreover, the dual solution of the problem should also be generalized. Additional conditions:<br>
- If OUT(i)-IN(i)<m_u(i), then p(i)<=0.<br>
- If OUT(i)-IN(i)>m_l(i), then p(i)>=0.<br>
Where p(i) denotes the potential of i.<br>
<br>
Consequences:<br>
- If m_l(i)<OUT(i)-IN(i)<m_u(i), then p(i)=0.<br>
- If m_l(i)=OUT(i)-IN(i)=m_u(i), then p(i) is unrestricted in sign.<br>
<br>
Regards,<br>
Peter<br>
<br>
<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div class="im">
Hi Peter,<br>
<br>
Could you tell me how difficult would it be to implement Network Simplex<br>
to solve a for compatible to the one used by the LP solvers i.e.<br>
<br>
m_l<=Ax<=m_u<br>
l<=x<=u<br>
<br>
in other words we give both a lower and an upper bound on the excess for<br>
each node?<br>
<br>
<br>
Regards,<br>
Alpar<br>
<br>
<br>
On Fri, 2010-04-23 at 01:52 +0000, Kovács Péter wrote:<br>
</div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
Dear Matt,<br>
<br>
You're right: the network is also extended inside the algorithms to support inequality for all nodes. Currently, the mixed case is not supported, neither in the interface nor in the implementation. If you need mixed conditions (= and >=), then it is a clear overhead that the graph is extendedtwice. However, it wouldn't be diffcult to handle all requirements at once, but the current interface is not capable for supporting mixed conditions.<div class="im">
<br>
<br>
I think a compatible extension of the interface could be an overloaded supplyMap() function, for which a Node->Value map and a Node->bool map should be passed. The first map specifies the supply values on the right hand side of the constraints, while the bool map indicates whetwer we require = or >= constraints. (NetworkSimplex also supports <= instead of >=, see the supplyType() function.)<br>
<br></div>
If you could implement this extension, we would be pleased to include itin the next major release.<div><div></div><div class="h5"><br>
<br>
Regards,<br>
Peter<br>
<br>
<br>
2010.04.23. 2:47 keltezéssel, Matthew Galati írta:<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
Peter - Thank you very much for the reply. I have the 2nd case - so it<br>
seems, I will need to expand my input graph. I saw in the source code<br>
that the graph is already expanded in a similar manner (for detecting<br>
infeasibility). However, this seems to be for the case when all flow<br>
balance constraints are either >= or <=. The mixed case does not seem to<br>
be handled.<br>
<br>
I will try changing the input graph and let you know if I have any<br>
difficulty.<br>
<br>
Thanks,<br>
Matt<br>
<br>
<br>
<br>
2010/4/22 Kovács Péter <<a href="mailto:kpeter@inf.elte.hu" target="_blank">kpeter@inf.elte.hu</a> <mailto:<a href="mailto:kpeter@inf.elte.hu" target="_blank">kpeter@inf.elte.hu</a>>><br>
<br>
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 onlyif<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, thenyou<br>
obtain an optimal solution for the original problem.<br>
<br>
Regards,<br>
Peter<br>
<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>
> <<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>
> the general form, so if you need the equality form, you have to<br>
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 wantto<br>
ensure<br>
> equality. Let's also assume that sum{ i} supply[i] != 0. That is,<br>
the =<br>
> and >= are not equivalent. This equality is "another constraint".<br>
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<br>
constraint or<br>
> the other as = vs >=0?<br>
><br>
> Thanks,<br>
> Matt<br>
><br>
><br>
<br>
<br>
</blockquote>
_______________________________________________<br>
Lemon-user mailing list<br>
<a href="mailto:Lemon-user@lemon.cs.elte.hu" target="_blank">Lemon-user@lemon.cs.elte.hu</a><br>
<a href="http://lemon.cs.elte.hu/mailman/listinfo/lemon-user" target="_blank">http://lemon.cs.elte.hu/mailman/listinfo/lemon-user</a><br>
</div></div></blockquote>
<br>
<br>
</blockquote>
<br>
<br>
<br>
</blockquote></div><br>