Maximum Flow

Here we have a graph of six nodes each of which have an input and output. The goal is to determine the optimal flow through the graph. This is done by maximizing the inputs to the starting nodes as much as possible.

We label each pathway between node. And we create a pseudo source and sink nodes—zero and seven respectively—to properly capture the initial inputs and final outputs in the graph. Note for each node that the flow conservation must be preserved. With this in mind we now have the following model

Maximize:
  \$x_01 + x_02 + x_03\$
subject to:
  node 1 \$x_01 = x_14 + x_15\$
  node 2 \$x_02 = x_24 + x_25 + x_26\$
  node 3 \$x_03 = x_35\$
  node 4 \$x_47 = x_14 + x_24\$
  node 5 \$x_57 = x_15 + x_25 + x_35\$
  node 6 \$x_26 = x_67\$
where:
  \$x_01 <= 3\$ \$x_02 <= 2\$ \$x_03 <= 2\$
  \$x_14 <= 5\$ \$x_15 <= 1\$ \$x_24 <= 1\$
  \$x_25 <= 3\$ \$x_26 <= 1\$ \$x_35 <= 1\$
  \$x_47 <= 4\$ \$x_57 <= 2\$ \$x_67 <= 4\$

let x01 = Variable.real "0->1" 0 3 |> toExpression
let x02 = Variable.real "0->2" 0 2 |> toExpression
let x03 = Variable.real "0->3" 0 2 |> toExpression

let x14 = Variable.real "1->4" 0 5 |> toExpression
let x15 = Variable.real "1->5" 0 1 |> toExpression

let x24 = Variable.real "2->4" 0 1 |> toExpression
let x25 = Variable.real "2->5" 0 3 |> toExpression
let x26 = Variable.real "2->6" 0 1 |> toExpression

let x35 = Variable.real "3->5" 0 1 |> toExpression

let x47 = Variable.real "4->7" 0 4 |> toExpression

let x57 = Variable.real "5->7" 0 2 |> toExpression

let x67 = Variable.real "6->7" 0 4 |> toExpression

let mdl =
  Model.Default
  |> DecisionVars [x01; x02; x03; x14; x15; x24; x25; x26; x35; x47; x57; x67]
  |> Goal Maximize
  |> Objective (x01 + x02 + x03)
  |> Constraints [
        x01 + -1*x14 + -1*x15 === 0 // node 1
        x02 + -1*x24 + -1*x25 + -1*x26 === 0 // node 2
        x03 + -1*x35 === 0 // node 3
        x14 + x24 + -1*x47 === 0 // node 4
        x15 + x25 + x35 + -1*x57 === 0 // node 5
        x26 + -1*x67 === 0 // node 6
      ]

let result = Solve mdl

match result with
| Solution sol ->
    printfn "Objective:%f" sol.Objective.toFloat
    sol.Variables |> Map.iter (fun k v -> printfn "%s: %f" k v)
| Error e ->
    printfn "%A" e

OUTPUT:

Objective:6.000000
0->1: 3.000000
0->2: 2.000000
0->3: 1.000000
1->4: 3.000000
1->5: 0.000000
2->4: 1.000000
2->5: 0.000000
2->6: 1.000000
3->5: 1.000000
4->7: 4.000000
5->7: 1.000000
6->7: 1.000000

Maximum Flow (Google.Graph)

Another method to solve flow networks is with the API Google.Graph. We instantiate a MaxFlow object and add the arcs with their respective capacities. Then solve. Pretty easy.

let numNodes = 6;
let numArcs = 9;
let tails = [0; 0; 0; 0; 1; 2; 3; 3; 4]
let heads = [1; 2; 3; 4; 3; 4; 4; 5; 5]
let capacities = [5L; 8L; 5L; 3L; 4L; 5L; 6L; 6L; 4L]
let expectedFlows = [4; 4; 2; 0; 4; 4; 0; 6; 4]
let expectedTotalFlow = 10;
let maxFlow = new MaxFlow()

for i=0 to (numArcs-1) do
  let arc = maxFlow.AddArcWithCapacity(tails.[i], heads.[i], capacities.[i])
  if (arc <> i) then
    failwith "Internal error"

let source = 0;
let sink = numNodes - 1;
printfn "Solving max flow with %i nodes, and %i arcs, source=%i, sink=%i " numNodes numArcs source sink
let solveStatus = maxFlow.Solve(source, sink)

match solveStatus with
| x when x = MaxFlow.Status.OPTIMAL ->
    let totalFlow = maxFlow.OptimalFlow();
    printfn "total computed flow %i, expected = %i" totalFlow expectedTotalFlow

    for i=1 to numArcs do
      printfn "Arc %i (%i -> %i), capacity=%i, computed=%i, expected=%i" i (maxFlow.Head(i-1)) (maxFlow.Tail(i-1)) (maxFlow.Capacity(i-1)) (maxFlow.Flow(i-1)) (expectedFlows.[i-1])
| _ ->
  printfn "Solving the max flow problem failed. Solver status: %s" (solveStatus.ToString("g"))

OUTPUT:

Solving max flow with 6 nodes, and 9 arcs, source=0, sink=5
total computed flow 10, expected = 10
Arc 1 (1 -> 0), capacity=5, computed=4, expected=4
Arc 2 (2 -> 0), capacity=8, computed=4, expected=4
Arc 3 (3 -> 0), capacity=5, computed=2, expected=2
Arc 4 (4 -> 0), capacity=3, computed=0, expected=0
Arc 5 (3 -> 1), capacity=4, computed=4, expected=4
Arc 6 (4 -> 2), capacity=5, computed=4, expected=4
Arc 7 (4 -> 3), capacity=6, computed=0, expected=0
Arc 8 (5 -> 3), capacity=6, computed=6, expected=6
Arc 9 (5 -> 4), capacity=4, computed=4, expected=4