Minimum Cost Flows

The min cost flow problem

Closely related to the max flow problem is the minimum cost (min cost) flow problem, in which each arc in the graph has a unit cost for transporting material across it. The problem is to find a flow with the least total cost.

The min cost flow problem also has special nodes, called supply nodes or demand nodes, which are similar to the source and sink in the max flow problem. Material is transported from supply nodes to demand nodes.

  • At a supply node, a positive amount — the supply — is added to the flow. A supply could represent production at that node, for example.
  • At a demand node, a negative amount — the demand — is taken away from the flow. A demand could represent consumption at that node, for example.

For convenience, we'll assume that all nodes, other than supply or demand nodes, have zero supply (and demand) .

For the min cost flow problem, we have the following flow conservation rule, which takes the supplies and demands into account:

The graph below shows a min cost flow problem. The arcs are labeled with pairs of numbers: the first number is the capacity and the second number is the cost. The numbers in parentheses next to the nodes represent supplies or demands. Node 0 is a supply node with supply 20, while nodes 3 and 4 are demand nodes, with demands -5 and -15, respectively.

(15, 4) (20, 2) (10, 6) (4, 2) (15, 1) (8, 4) (5, 3) (4, 1) (20, 2) (20) (0) (0) (-5) (-15) 0 1 2 3 4

Define the data

The following code defines the data for the problem. In this case, there are four arrays for the start nodes, end nodes, capacities, and unit costs. Again, the length of the arrays is the number of arcs in the graph.

Python data
  # Define four parallel arrays: start_nodes, end_nodes, capacities, and unit costs
  # between each pair. For instance, the arc from node 0 to node 1 has a
  # capacity of 15 and a unit cost of 4.

  start_nodes = [0, 0, 1, 1, 1, 2, 2, 3, 4]
  end_nodes = [1, 2, 2, 3, 4, 3, 4, 4, 2]
  capacities = [15, 8, 20, 4, 10, 15, 5, 20, 4]
  unit_costs = [4, 4, 2, 2, 6, 1, 3, 2, 3]

  # Define an array of supplies at each node.

  supplies = [20, 0, 0, -5, -15]
C# data
    // Define four parallel arrays: sources, destinations, capacities, and unit costs
    // between each pair. For instance, the arc from node 0 to node 1 has a
    // capacity of 15.
    // Problem taken From Taha's 'Introduction to Operations Research',
    // example 6.4-2.

    int numNodes = 5;
    int numArcs = 9;
    int[] startNodes = {0, 0, 1, 1, 1, 2, 2, 3, 4};
    int[] endNodes = {1, 2, 2, 3, 4, 3, 4, 4, 2};
    int[] capacities = {15, 8, 20, 4, 10, 15, 5, 20, 4};
    int[] unitCosts = {4, 4, 2, 2, 6, 1, 3, 2, 3};

    // Define an array of supplies at each node.

    int[] supplies = {20, 0, 0, -5, -15};

Declare the solver and add the arcs

To solve the problem, we use the SimpleMinCostFlow solver. (The C# name for the solver is MinCostFlow.)

For each start node and end node, we create an arc from start node to end node with the given capacity and unit cost, using the method AddArcWithCapacityAndUnitCost.

The solver's SetNodeSupply method creates a vector of supplies for the nodes.

Python constraints
  # Instantiate a SimpleMinCostFlow solver.
  min_cost_flow = pywrapgraph.SimpleMinCostFlow()

  # Add each arc.
  for i in range(0, len(start_nodes)):
    min_cost_flow.AddArcWithCapacityAndUnitCost(start_nodes[i], end_nodes[i],
                                                capacities[i], unit_costs[i])

  # Add node supplies.

  for i in range(0, len(supplies)):
    min_cost_flow.SetNodeSupply(i, supplies[i])
C# constraints
    // Instantiate a SimpleMinCostFlow solver.
    MinCostFlow minCostFlow = new MinCostFlow();

    // Add each arc.
    for (int i = 0; i < numArcs; ++i)
    {
      int arc = minCostFlow.AddArcWithCapacityAndUnitCost(startNodes[i], endNodes[i],
                                           capacities[i], unitCosts[i]);
      if (arc != i) throw new Exception("Internal error");
    }

     // Add node supplies.
    for (int i = 0; i < numNodes; ++i)
    {
      minCostFlow.SetNodeSupply(i, supplies[i]);
    }

Invoke the solver and display the results

Now that all the arcs have been defined, all that remains is to invoke the solver and display the results. We invoke the Solve() method, and then display the flow and cost across each arc.

Python solution
  # Find the minimum cost flow between node 0 and node 4.
  if min_cost_flow.Solve() == min_cost_flow.OPTIMAL:
    print('Minimum cost:', min_cost_flow.OptimalCost())
    print('')
    print('  Arc    Flow / Capacity  Cost')
    for i in range(min_cost_flow.NumArcs()):
      cost = min_cost_flow.Flow(i) * min_cost_flow.UnitCost(i)
      print('%1s -> %1s   %3s  / %3s       %3s' % (
          min_cost_flow.Tail(i),
          min_cost_flow.Head(i),
          min_cost_flow.Flow(i),
          min_cost_flow.Capacity(i),
          cost))
  else:
    print('There was an issue with the min cost flow input.')
C# solution
    //Console.WriteLine("Solving min cost flow with " + numNodes + " nodes, and " +
    //                  numArcs + " arcs, source=" + source + ", sink=" + sink);

    // Find the min cost flow.
    int solveStatus = minCostFlow.Solve();
    if (solveStatus == MinCostFlow.OPTIMAL)
    {
      long optimalCost = minCostFlow.OptimalCost();
      Console.WriteLine("Minimum cost: " + optimalCost);
      Console.WriteLine("");
      Console.WriteLine(" Edge   Flow / Capacity  Cost");
      for (int i = 0; i < numArcs; ++i)
      {
        long cost = minCostFlow.Flow(i) * minCostFlow.UnitCost(i);
        Console.WriteLine(minCostFlow.Tail(i) + " -> " +
                          minCostFlow.Head(i) + "  " +
                          string.Format("{0,3}",  minCostFlow.Flow(i)) + "  / " +
                          string.Format ("{0,3}", minCostFlow.Capacity(i)) + "       " +
                          string.Format ("{0,3}", cost));
      }
    }
    else
    {
      Console.WriteLine("Solving the min cost flow problem failed. Solver status: " +
                        solveStatus);
    }
  }
Here is the output of the Python program:
    $ PYTHONPATH=src python examples/python/min_cost_flow.py
    Minimum cost: 150

      Arc    Flow / Capacity  Cost
    0 -> 1    12  /  15        48
    0 -> 2     8  /   8        32
    1 -> 2     8  /  20        16
    1 -> 3     4  /   4         8
    1 -> 4     0  /  10         0
    2 -> 3    11  /  15        11
    2 -> 4     5  /   5        15
    3 -> 4    10  /  20        20
    4 -> 2     0  /   4         0

Complete programs

Putting it all together, here are the complete programs in Python and C#.

Full Python program
# """From Bradley, Hax, and Magnanti, 'Applied Mathematical Programming', figure 8.1."""

from __future__ import print_function
from ortools.graph import pywrapgraph

def main():
  """MinCostFlow simple interface example."""

  # Define four parallel arrays: start_nodes, end_nodes, capacities, and unit costs
  # between each pair. For instance, the arc from node 0 to node 1 has a
  # capacity of 15 and a unit cost of 4.

  start_nodes = [0, 0, 1, 1, 1, 2, 2, 3, 4]
  end_nodes = [1, 2, 2, 3, 4, 3, 4, 4, 2]
  capacities = [15, 8, 20, 4, 10, 15, 5, 20, 4]
  unit_costs = [4, 4, 2, 2, 6, 1, 3, 2, 3]

  # Define an array of supplies at each node.

  supplies = [20, 0, 0, -5, -15]


  # Instantiate a SimpleMinCostFlow solver.
  min_cost_flow = pywrapgraph.SimpleMinCostFlow()

  # Add each arc.
  for i in range(0, len(start_nodes)):
    min_cost_flow.AddArcWithCapacityAndUnitCost(start_nodes[i], end_nodes[i],
                                                capacities[i], unit_costs[i])

  # Add node supplies.

  for i in range(0, len(supplies)):
    min_cost_flow.SetNodeSupply(i, supplies[i])


  # Find the minimum cost flow between node 0 and node 4.
  if min_cost_flow.Solve() == min_cost_flow.OPTIMAL:
    print('Minimum cost:', min_cost_flow.OptimalCost())
    print('')
    print('  Arc    Flow / Capacity  Cost')
    for i in range(min_cost_flow.NumArcs()):
      cost = min_cost_flow.Flow(i) * min_cost_flow.UnitCost(i)
      print('%1s -> %1s   %3s  / %3s       %3s' % (
          min_cost_flow.Tail(i),
          min_cost_flow.Head(i),
          min_cost_flow.Flow(i),
          min_cost_flow.Capacity(i),
          cost))
  else:
    print('There was an issue with the min cost flow input.')

if __name__ == '__main__':
  main()
Full C# program
// """From Bradley, Hax, and Magnanti, 'Applied Mathematical Programming', figure 8.1."""

using System;
using Google.OrTools.Graph;

public class CsFlow
{
  private static void SolveMinCostFlow()
  {
    // Define four parallel arrays: sources, destinations, capacities, and unit costs
    // between each pair. For instance, the arc from node 0 to node 1 has a
    // capacity of 15.
    // Problem taken From Taha's 'Introduction to Operations Research',
    // example 6.4-2.

    int numNodes = 5;
    int numArcs = 9;
    int[] startNodes = {0, 0, 1, 1, 1, 2, 2, 3, 4};
    int[] endNodes = {1, 2, 2, 3, 4, 3, 4, 4, 2};
    int[] capacities = {15, 8, 20, 4, 10, 15, 5, 20, 4};
    int[] unitCosts = {4, 4, 2, 2, 6, 1, 3, 2, 3};

    // Define an array of supplies at each node.

    int[] supplies = {20, 0, 0, -5, -15};



    // Instantiate a SimpleMinCostFlow solver.
    MinCostFlow minCostFlow = new MinCostFlow();

    // Add each arc.
    for (int i = 0; i < numArcs; ++i)
    {
      int arc = minCostFlow.AddArcWithCapacityAndUnitCost(startNodes[i], endNodes[i],
                                           capacities[i], unitCosts[i]);
      if (arc != i) throw new Exception("Internal error");
    }

     // Add node supplies.
    for (int i = 0; i < numNodes; ++i)
    {
      minCostFlow.SetNodeSupply(i, supplies[i]);
    }


    //Console.WriteLine("Solving min cost flow with " + numNodes + " nodes, and " +
    //                  numArcs + " arcs, source=" + source + ", sink=" + sink);

    // Find the min cost flow.
    int solveStatus = minCostFlow.Solve();
    if (solveStatus == MinCostFlow.OPTIMAL)
    {
      long optimalCost = minCostFlow.OptimalCost();
      Console.WriteLine("Minimum cost: " + optimalCost);
      Console.WriteLine("");
      Console.WriteLine(" Edge   Flow / Capacity  Cost");
      for (int i = 0; i < numArcs; ++i)
      {
        long cost = minCostFlow.Flow(i) * minCostFlow.UnitCost(i);
        Console.WriteLine(minCostFlow.Tail(i) + " -> " +
                          minCostFlow.Head(i) + "  " +
                          string.Format("{0,3}",  minCostFlow.Flow(i)) + "  / " +
                          string.Format ("{0,3}", minCostFlow.Capacity(i)) + "       " +
                          string.Format ("{0,3}", cost));
      }
    }
    else
    {
      Console.WriteLine("Solving the min cost flow problem failed. Solver status: " +
                        solveStatus);
    }
  }

  static void Main()
  {
    SolveMinCostFlow();
  }
}

SimpleMinCostFlow methods

The SimpleMinCostFlow Flow class provides the following methods, most of which are not used in the preceding example:

  • AddArcWithCapacityAndUnitCost()
  • SetNodeSupply()
  • Head()
  • NumArcs()
  • NumNodes()
  • MaximumFlow()
  • OptimalCost()
  • Solve()
  • SolveMaxFlowWithMinCost()
  • Tail()

More detail on each of these is available in the SimpleMinCostFlow reference page.

Send feedback about...

Optimization
Optimization