Opened 2 years ago

Closed 22 months ago

# Getting the node potentials in min cost flow

Reported by: Owned by: matheusota Alpar Juttner major LEMON 1.4 release core hg main

### 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

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

### 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 new → closed
Note: See TracTickets for help on using tickets.