Opened 2 years ago
Closed 22 months ago
#663 closed defect (invalid)
Getting the node potentials in min cost flow
Reported by: | matheusota | Owned by: | Alpar Juttner |
---|---|---|---|
Priority: | major | Milestone: | LEMON 1.4 release |
Component: | core | Version: | hg main |
Keywords: | Cc: | ||
Revision id: |
Description
Hi,
I'm interested in getting the dual solution of a min-cost s-t flow problem. I executed the Network Simplex algorithm using
NS::ProblemType status = ns.run()
and afterwards I set the node potentials with
ns.potentialMap(dualNodeValues)
However, when I compute the objective function of the dual (by setting the dual of each edge to be the maximum between 0 and the negative of the reduced cost), it does not match the objective function of the primal (the value of the min-cost flow). I'm suspecting that, because the problem was solved in a single iteration (after finding a max-flow), the duals are not correctly set.
I say that because, in my understanding, the duals should be the value of the shortest paths starting at t in the residual graph. So I computed these by hand and it does not match the values I obtain from lemon. Is there a way that I can update the dual values (without me having to manually create the residual graph and running a shortest path algorithm)?
Thanks! Matheus
Attachments (1)
Change History (4)
comment:1 Changed 2 years ago by
Changed 2 years ago by
Attachment: | mcf_example.png added |
---|
comment:2 Changed 2 years ago by
Hi, I checked it again, and the duals are correct, sorry for the mistake. Indeed all the reduced costs are non-negative in the residual graph. I think the standard "textbook way" of getting the duals once you have the primal solution is by running a shortest path algorithm from t (in the case you are looking for an r-t flow). So I was expecting the duals to be like that. The duals returned by Lemon is not like that, but it is also feasible (and optimal).
I will just manually create the residual graph and compute the duals using that method I described (I need them to be in that format).
Best, Matheus
comment:3 Changed 22 months ago by
Resolution: | → invalid |
---|---|
Status: | new → closed |
The dual solution of the min-cost flow problem, and even the min-cost flow problem itself can be defined in different ways. LEMON uses this formulation: http://lemon.cs.elte.hu/pub/doc/1.3.1/a00010.html
In particular, we define the reduced cost function this way:
cost_reduced(uv) = cost(uv) + potential(u) - potential(v)
. And in the residual graph, this reduced cost should be non-negative for each arc (with positive residual capacity). In terms of the original graph, the optimality conditions are a bit more complicated, they are described by the documentation linked above.Could you describe more precisely what is the issue with the potentials provided by
NetworkSimplex
? Could you check them on a simple example that is easy to verify manually? (E.g. for the network shown by the image I attached to this ticket.)