Min-cost flow
LightGraphsFlows.mincost_flow
— Function.mincost_flow(graph, capacity, demand, cost, solver, [, source][, sink])
Find a flow satisfying the demand
and capacity
constraints for each edge while minimizing the sum(cost.*flow)
.
If
source
andsink
are specified, they are allowed a net flow production,
consumption respectively. All other nodes must respect the flow conservation property.
The problem can be seen as a linear programming problem and uses a LP
solver under the hood. We use Clp in the examples and tests.
Returns a flow matrix, flow[i,j] corresponds to the flow on the (i,j) arc.
Usage Example:
julia> using Clp: ClpSolver # use your favorite LP solver here
julia> g = lg.DiGraph(6) # Create a flow-graph
julia> lg.add_edge!(g, 5, 1)
julia> lg.add_edge!(g, 5, 2)
julia> lg.add_edge!(g, 3, 6)
julia> lg.add_edge!(g, 4, 6)
julia> lg.add_edge!(g, 1, 3)
julia> lg.add_edge!(g, 1, 4)
julia> lg.add_edge!(g, 2, 3)
julia> lg.add_edge!(g, 2, 4)
julia> w = zeros(6,6)
julia> w[1,3] = 10.
julia> w[1,4] = 5.
julia> w[2,3] = 2.
julia> w[2,4] = 2.
julia> # v2 -> sink have demand of one
julia> demand = spzeros(6,6)
julia> demand[3,6] = 1
julia> demand[4,6] = 1
julia> capacity = ones(6,6)
julia> flow = mincost_flow(g, capacity, demand, w, ClpSolver(), 5, 6)