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

[Alpár Jüttner]

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 extended twice. 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 it in 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 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
> >      >
> >      >
> > 
> > 
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user