Minimum-cost flow problem

Question

A flow network is a directed graph G = (V, E) with a source vertex s ϵ V and a sink vertex t ϵ V, and where every edge (u, v) ϵ E on the graph (connecting nodes u ϵ V and v ϵ V) has 2 quantities associated with it:

1. c(u, v) >= 0, the capacity of the edge
2. a(u, v) >= 0, the cost of sending one unit through the edge

We define a function 0 <= f(u, v) <= c(u, v) to be the number of units being passed through a given edge (u, v). Thus, the cost for a given edge (u, v) is a(u, v) * f(u, v). The minimum-cost flow problem is defined as minimizing the total cost over all edges for a given flow amount d, given by the following quantity:

The following constraints apply to the problem:

1. Capacity requirements: the flow through a given edge may not exceed the capacity of that edge (f(u, v) <= c(u, v)).
2. Skew symmetry: the flow though a given edge must be antisymmetric when the direction is reversed (f(u, v) = -f(v, u)).
3. Flow conservation: the net flow into any non-sink non-source node must be 0 (for each u ∉ {s, t}, summing over all w, sum f(u, w) = 0).
4. Required flow: the net flow out of the source and the net flow into the sink must both equal the required flow through the network (summing over all u, sum f(s, u) = sum f(u, t) = d).

Given a flow network G and a required flow d, output the minimum cost for sending d units through the network. You may assume that a solution exists. d and all capacities and costs will be non-negative integers. For a network with N vertices labeled with [0, N-1], the source vertex will be 0 and the sink vertex will be N-1.

This is code-golf, so the shortest answer (in bytes) wins. Remember that this is a competition within languages as well as between languages, so don't be afraid to post a solution in a verbose language.

Built-ins are allowed, but you are encouraged to include solutions without builtins, either as an additional solution in the same answer, or as an independent answer.

Input may be in any reasonable manner that includes the capacities and costs of each edge and the demand.

Test Cases

Test cases are provided in the following format:

c=<2D matrix of capacities> a=<2D matrix of costs> d=<demand> -> <solution>

c=[[0, 3, 2, 3, 2], [3, 0, 5, 3, 3], [2, 5, 0, 4, 5], [3, 3, 4, 0, 4], [2, 3, 5, 4, 0]] a=[[0, 1, 1, 2, 1], [1, 0, 1, 2, 3], [1, 1, 0, 2, 2], [2, 2, 2, 0, 3], [1, 3, 2, 3, 0]] d=7 -> 20
c=[[0, 1, 1, 5, 4], [1, 0, 2, 4, 2], [1, 2, 0, 1, 1], [5, 4, 1, 0, 3], [4, 2, 1, 3, 0]] a=[[0, 1, 1, 2, 2], [1, 0, 2, 4, 1], [1, 2, 0, 1, 1], [2, 4, 1, 0, 3], [2, 1, 1, 3, 0]] d=7 -> 17
c=[[0, 1, 4, 5, 4, 2, 3], [1, 0, 5, 4, 3, 3, 5], [4, 5, 0, 1, 5, 5, 5], [5, 4, 1, 0, 3, 2, 5], [4, 3, 5, 3, 0, 4, 4], [2, 3, 5, 2, 4, 0, 2], [3, 5, 5, 5, 4, 2, 0]] a=[[0, 1, 4, 2, 4, 1, 1], [1, 0, 3, 2, 2, 1, 1], [4, 3, 0, 1, 4, 5, 2], [2, 2, 1, 0, 2, 2, 3], [4, 2, 4, 2, 0, 4, 1], [1, 1, 5, 2, 4, 0, 2], [1, 1, 2, 3, 1, 2, 0]] d=10 -> 31
c=[[0, 16, 14, 10, 14, 11, 10, 4, 3, 16], [16, 0, 18, 19, 1, 6, 10, 19, 5, 4], [14, 18, 0, 2, 15, 9, 3, 14, 20, 13], [10, 19, 2, 0, 2, 10, 12, 17, 19, 22], [14, 1, 15, 2, 0, 11, 23, 25, 10, 19], [11, 6, 9, 10, 11, 0, 14, 16, 25, 4], [10, 10, 3, 12, 23, 14, 0, 11, 7, 8], [4, 19, 14, 17, 25, 16, 11, 0, 14, 5], [3, 5, 20, 19, 10, 25, 7, 14, 0, 22], [16, 4, 13, 22, 19, 4, 8, 5, 22, 0]] a=[[0, 12, 4, 2, 9, 1, 1, 3, 1, 6], [12, 0, 12, 16, 1, 2, 9, 13, 2, 3], [4, 12, 0, 2, 2, 2, 2, 10, 1, 1], [2, 16, 2, 0, 2, 1, 8, 4, 4, 2], [9, 1, 2, 2, 0, 5, 6, 23, 5, 8], [1, 2, 2, 1, 5, 0, 13, 12, 12, 1], [1, 9, 2, 8, 6, 13, 0, 9, 4, 4], [3, 13, 10, 4, 23, 12, 9, 0, 13, 1], [1, 2, 1, 4, 5, 12, 4, 13, 0, 13], [6, 3, 1, 2, 8, 1, 4, 1, 13, 0]] d=50 -> 213

These test cases were computed with the NetworkX Python library.

Answer 1

[R + lpSolve], 201 186 149 144 bytes

function(c,a,d,`^`=rep,N=ncol(c),G=diag(N),P=t(1^N),M=P%x%G+G%x%-P)lpSolve::lp(,a,rbind(M,diag(N*N)),c('=','<')^c(N,N*N),c(d,0^(N-2),-d,c))$objv

Try it online!

The code constructs the following Linear Problem and solve it using lpSolve package :

$$ \begin{align} min & \sum_{\forall x \in V}\ \sum_{\forall y \in V} A_{x,y} \cdot f_{x,y} \\ subject\ to : & \\ & \sum_{x \in V} f_{v,x} - f_{x,v} = 0 & \forall v \in V : v \neq \{s,t\} \\ & \sum_{x \in V} f_{s,x} - f_{x,s} = d \\ & \sum_{x \in V} f_{t,x} - f_{x,t} = -d \\ & f_{x,b} \leq C_{x,b} & \forall x \in V,\forall y \in V \end{align} $$ where :

• \$V\$ is the set of vertices
• \$s\$ s is the source vertex
• \$t\$ s is the target (or sink) vertex
• \$A_{x,y}\$ is the flow cost for edge x -> y
• \$f_{x,y}\$ is the flow of edge x -> y in the optimal solution
• \$d\$ is the required flow at sink (i.e. the demand at \$t\$ and the production at \$s\$)
• \$C_{x,y}\$ is the maximum capacity of edge x -> y

Answer 2

Wolfram Language, 42 bytes

FindMinimumCostFlow[#,1,VertexCount@#,#2]&

Trivial builtin. Non-builtin solution coming soon.

Answer 3

Python 3 + NetworkX, 137 bytes

from networkx import*
def f(g,d,z='demand'):N=len(g)**.5//1;G=DiGraph(g);G.node[0][z]=-d;G.node[N-1][z]=d;return min_cost_flow_cost(G)

No TryItOnline link because TIO doesn't have the NetworkX library installed

Takes graph input as an edge list with capacity and weight attributes, like this:

[(0, 0, {'capacity': 0, 'weight': 0}), (0, 1, {'capacity': 3, 'weight': 1}), (0, 2, {'capacity': 2, 'weight': 1}), (0, 3, {'capacity': 3, 'weight': 2}), (0, 4, {'capacity': 2, 'weight': 1}), (1, 0, {'capacity': 3, 'weight': 1}), (1, 1, {'capacity': 0, 'weight': 0}), (1, 2, {'capacity': 5, 'weight': 1}), (1, 3, {'capacity': 3, 'weight': 2}), (1, 4, {'capacity': 3, 'weight': 3}), (2, 0, {'capacity': 2, 'weight': 1}), (2, 1, {'capacity': 5, 'weight': 1}), (2, 2, {'capacity': 0, 'weight': 0}), (2, 3, {'capacity': 4, 'weight': 2}), (2, 4, {'capacity': 5, 'weight': 2}), (3, 0, {'capacity': 3, 'weight': 2}), (3, 1, {'capacity': 3, 'weight': 2}), (3, 2, {'capacity': 4, 'weight': 2}), (3, 3, {'capacity': 0, 'weight': 0}), (3, 4, {'capacity': 4, 'weight': 3}), (4, 0, {'capacity': 2, 'weight': 1}), (4, 1, {'capacity': 3, 'weight': 3}), (4, 2, {'capacity': 5, 'weight': 2}), (4, 3, {'capacity': 4, 'weight': 3}), (4, 4, {'capacity': 0, 'weight': 0})]

This is a golfed version of the code that I used to verify the test cases.