Min-cost flow

GraphsFlows.mincost_flowFunction
function mincost_flow(g::AbstractGraph,
		node_demand::AbstractVector,
		edge_capacity::AbstractMatrix,
		edge_cost::AbstractMatrix,
		optimizer;
		edge_demand::Union{Nothing,AbstractMatrix} = nothing,
		source_nodes = (),
		sink_nodes = ()
		)

Find a flow over a directed graph g satisfying the node_demand at each node and edge_capacity constraints for each edge while minimizing dot(edge_cost, flow).

Returns a sparse flow matrix, flow[i,j] corresponds to the flow on the (i,j) arc.

Arguments

  • g is a directed Graphs.AbstractGraph.

-node_demand is a vector of nodal demand values, which should be negative for sources, positive for sink nodes, and zero for all other nodes.

  • edge_capacity::AbstractMatrix sets an upper bound on the flow of each arc.
  • edge_cost::AbstractMatrix the cost per unit of flow on each arc.
  • optimizer is an optimizer constructor, like Clp.Optimizer or () -> Clp.Optimizer() passed at the construction of the JuMP.Model.

Keyword arguments

  • edge_demand::Union{Nothing,AbstractMatrix}: require a minimum flow for edges, or nothing.
  • source_nodes Collection of sources at which the nodal netflow is allowed to be greater than nodal demand, defaults to an empty tuple.
  • sink_nodes Collection of sinks at which the nodal netflow is allowed to be less than nodal demand, defaults to an empty tuple.

source_nodes & sink_nodes are only needed when nodal flow are not explictly set in node_demand

Usage Example:

julia> import Graphs
julia> using GraphsFlows: mincost_flow
julia> import Clp # use your favorite LP solver here
julia> using SparseArrays: spzeros
julia> g = Graphs.DiGraph(6) # Create a flow-graph
julia> Graphs.add_edge!(g, 5, 1)
julia> Graphs.add_edge!(g, 5, 2)
julia> Graphs.add_edge!(g, 3, 6)
julia> Graphs.add_edge!(g, 4, 6)
julia> Graphs.add_edge!(g, 1, 3)
julia> Graphs.add_edge!(g, 1, 4)
julia> Graphs.add_edge!(g, 2, 3)
julia> Graphs.add_edge!(g, 2, 4)
julia> cost = zeros(6,6)
julia> cost[1,3] = 10
julia> cost[1,4] = 5
julia> cost[2,3] = 2
julia> cost[2,4] = 2
julia> demand = spzeros(6)
julia> demand[5] = -2
julia> demand[6] = 2
julia> capacity = ones(6,6)
julia> flow = mincost_flow(g, demand, capacity, cost, Clp.Optimizer)
source