LightGraphsFlows.jl icon indicating copy to clipboard operation
LightGraphsFlows.jl copied to clipboard

mincost() return dual variables

Open Jacob-Stevens-Haas opened this issue 5 years ago • 7 comments

Is there a way to have mincost() return not just the solution variables, but also the dual variables? In the example posted, mincost() is passed Clpsolver(), which produces the dual variables already. For anyone unfamiliar with LP duality, these represent the subgradients of the min cost problem with respect to the arc constraints.

Since I need both the primal and dual variables, I'm currently converting the min cost problem to an LP and calling Clpsolver() directly. However, I'm not sure if mincost(), as written, takes advantage of reformatting the problem as a network simplex problem before passing it to Clpsolver(). I'd be missing out on that boost in speed with my current code.

Wikipedia says that network simplex "works very well in practice, typically 200 to 300 times faster than the simplex method applied to general linear program of same dimensions." (Although it does have a "citation needed" annotation)

Jacob-Stevens-Haas avatar Oct 20 '18 20:10 Jacob-Stevens-Haas