COIN-OR::LEMON - Graph Library

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:



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 =

and afterwards I set the node potentials with


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)

mcf_example.png (86.5 KB) - added by Peter Kovacs 2 years ago.

Download all attachments as: .zip

Change History (4)

comment:1 Changed 2 years ago by Peter Kovacs

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:

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

Changed 2 years ago by Peter Kovacs

Attachment: mcf_example.png added

comment:2 Changed 2 years ago by matheusota

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 Peter Kovacs

Resolution: invalid
Status: newclosed
Note: See TracTickets for help on using tickets.