Skip to content
This repository has been archived by the owner on Oct 22, 2021. It is now read-only.

mincost() return dual variables #20

Open
Jacob-Stevens-Haas opened this issue Oct 20, 2018 · 7 comments
Open

mincost() return dual variables #20

Jacob-Stevens-Haas opened this issue Oct 20, 2018 · 7 comments

Comments

@Jacob-Stevens-Haas
Copy link

Jacob-Stevens-Haas commented Oct 20, 2018

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
Copy link
Member

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
Copy link
Author

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
Copy link
Member

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
Copy link

caseykneale commented Feb 11, 2020

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
Copy link
Member

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
Copy link

caseykneale commented Feb 12, 2020

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
Copy link

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.

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
None yet
Projects
None yet
Development

No branches or pull requests

5 participants