mincost() return dual variables

[Jacob-Stevens-Haas]

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)

[matbesancon]

hi, sorry for the delay, it is indeed an interesting piece of information when solving flows.

Regarding network simplex this is correct, but I'm not sure you can pass this info without being solver-specific. If you look at Clp FAQ: https://www.coin-or.org/Clp/faq.html Implement a network simplex is still a todo

[Jacob-Stevens-Haas]

In general, it may not be possible to do in a solver-agnostic manner. But if the solver provides more than the primal solution, could mincost() return the extra objects in a tuple?

[matbesancon]

ah sorry, I miswrote it: getting the dual variables for the constraints should always be possible, it's using the specialized network simplex which is solver-dependent. For the API one thing we can do is return a FlowResult struct containing both the matrix of flows and dual variables

[caseykneale]

I think you all are talking about roughly the same thing I want. I'm not a mathematician, nor have I ever played one on TV. But I am really interested in getting flow paths, rather then just flows. For example: if I wanted to implement Earth Mover Distance using mincost_flow it might look something like the following:

a = [3,2,1]
a = a ./ sum(a)
b = [1,2,3]
b = b ./ sum(b)

len = length(a)
g = LightGraphs.DiGraph(len)
cost,demand,capacity = zeros(len,len), zeros(len,len),  ones(len,len)
for i in 1:len
    for j in 1:len
        LightGraphs.add_edge!(g, i, j)
        cost[i,j] = abs(j - i)
    end
    demand[i,i] = b[i]
end

flow = mincost_flow(g, capacity, demand, cost, ClpSolver())
#new api?
flow = mincost_flow(g, path,
                    capacity, cost, ClpSolver(),
                    edge_demand=demand)

but the Flow does not return the path/cost of the flow. It just gives ... b, which is pretty uninteresting. Granted I may have goofed in my implementation as well. I hope the idea is clear. If what i'm thinking is different should I file a different issue?

[etiennedeg]

Your problem is not the same as above, I think you misunderstand the entries of the algorithm. You only have positive demands, so no sinks. As the flow has nowhere to go, you retrieve the b value. You are probably confused by the fact that the library documentation use an example of the old syntax with the demand on edges (which is still possible to do). We whould update it with the example given for the method. (see mincost.jl )

To give you an example, to model the problem linked here: transportation problem you can use the following code (I filled the capacities with something big enough):

const lg = LightGraphs

g = lg.DiGraph(6) # Create a flow-graph
w = zeros(6,6)

lg.add_edge!(g, 1, 4)
w[1,4] = 3
lg.add_edge!(g, 1, 5)
w[1,5] = 1
lg.add_edge!(g, 2, 4)
w[2,4] = 4
lg.add_edge!(g, 2, 5)
w[2,5] = 2
lg.add_edge!(g, 2, 6)
w[2,6] = 4
lg.add_edge!(g, 3, 5)
w[3,5] = 3
lg.add_edge!(g, 3, 6)
w[3,6] = 3

demand = zeros(6)
demand[1] = 5
demand[2] = 7
demand[3] = 3
demand[4] = -7
demand[5] = -3
demand[6] = -5
capacity = fill(10, (6,6))
flow = mincost_flow(g, demand, capacity, w, ClpSolver())

The output will be:

6×6 SparseArrays.SparseMatrixCSC{Float64,Int64} with 7 stored entries:
  [1, 4]  =  2.0
  [2, 4]  =  5.0
  [1, 5]  =  3.0
  [2, 5]  =  0.0
  [3, 5]  =  0.0
  [2, 6]  =  2.0
  [3, 6]  =  3.0

Which is a sparse matrix with the desired flow values.

[caseykneale]

Thank you for your help! think I got a simple earth movers distance worked out using light graph flows now!

a = [3,2,1]
b = [1,2,3]
len = length(a)
g = LightGraphs.DiGraph(len)
cost,  capacity = zeros(len,len), ones(len,len)
demand = b .- a
for i in 1:len, j in 1:len
    if i != j
        LightGraphs.add_edge!(g, i, j)
        cost[i,j] = abs(j - i)# +1
    end
end

flow = mincost_flow(g, demand, capacity, cost, ClpSolver())
result = Matrix(flow)
cost
EMD = sum( flow .* cost )

Maybe this should be an example? I think there are packages dedicated to solving this type of problem.

[sbromberger]

Just a code optimization: it might be faster to create a complete_graph(len) outside of that loop. Adding edges one at a time can be a bit expensive.