Getting the node potentials in min cost flow

[matheusota]

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

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

[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