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

[Matthew Galati]

Hi. I would be very interested in using such extensions. Has this been
implemented yet? Or, are there any plans to implement this?

Thanks,
Matt






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

> Dear All,
>
> In short, we could implement the following extensions without serious
> difficulties and without running time overhead:
>
>  * 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.
>
>  * m_l<=Ax<=m_u support for the other MCF solvers if all values in m_l is
> finite (upper bounds could be infinite).
>
>
> In details:
>
> 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.)
>
> 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.
>
> 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.
>
> 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.
>
> 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?
>
> 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.)
>
>
> Moreover, the dual solution of the problem should also be generalized.
> Additional conditions:
>  - If OUT(i)-IN(i)<m_u(i), then p(i)<=0.
>  - If OUT(i)-IN(i)>m_l(i), then p(i)>=0.
> Where p(i) denotes the potential of i.
>
> Consequences:
>  - If m_l(i)<OUT(i)-IN(i)<m_u(i), then p(i)=0.
>  - If m_l(i)=OUT(i)-IN(i)=m_u(i), then p(i) is unrestricted in sign.
>
> Regards,
> Peter
>
>
>  Hi Peter,
>>
>> Could you tell me how difficult would it be to implement Network Simplex
>> to solve a for compatible to the one used by the LP solvers i.e.
>>
>> m_l<=Ax<=m_u
>> l<=x<=u
>>
>> in other words we give both a lower and an upper bound on the excess for
>> each node?
>>
>>
>> Regards,
>> Alpar
>>
>>
>> On Fri, 2010-04-23 at 01:52 +0000, Kovács Péter wrote:
>>
>>> Dear Matt,
>>>
>>> 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.
>>>
>>>
>>> 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.)
>>>
>>> If you could implement this extension, we would be pleased to include
>>> itin the next major release.
>>>
>>>
>>> Regards,
>>> Peter
>>>
>>>
>>> 2010.04.23. 2:47 keltezéssel, Matthew Galati írta:
>>>
>>>> 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 <mailto: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 onlyif
>>>>    the original problem is feasible. Moreover, if you restrict an
>>>> optimal
>>>>    solution of the new problem to the arcs of the original graph,
>>>> thenyou
>>>>    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 wantto
>>>>    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
>>>>     >
>>>>     >
>>>>
>>>>
>>>>  _______________________________________________
>>> Lemon-user mailing list
>>> Lemon-user at lemon.cs.elte.hu
>>> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>>>
>>
>>
>>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20100629/569e5ea5/attachment.html>