Assignment as a Minimum Cost Flow Problem

Overview

You can use the min cost flow solver to solve special cases of the assignment problem. In fact, min cost flow can often return a solution faster than either the MIP or CP-SAT solver. However, MIP and CP-SAT can solve a larger class of problems than min cost flow, so in most cases MIP or CP-SAT are the best choices.

The following sections present Python programs that solve the following assignment problems using the min cost flow solver:

Linear assignment example

This section show how to solve the example, described in the section Linear Assignment Solver, as a min cost flow problem.

Import the libraries

The following code imports the required library.

from ortools.graph import pywrapgraph

Declare the solver

The following code creates the minimum cost flow solver.

  min_cost_flow = pywrapgraph.SimpleMinCostFlow()

Create the data

The flow diagram for the problem consists of the bipartite graph for the cost matrix (see the assignment overview for a slightly different example), with a source and sink added.

Workers Tasks Source Sink 0 1 2 3 4 5 6 7 8 9

Note: The numbering of the workers and tasks is slightly different than in the section Linear Assignment Solver, because the min cost flow solver requires all nodes in the graph to be numbered distinctly

The data contains the following four arrays, corresponding to the start nodes, end nodes, capacities, and costs for the problem. The length of each array is the number of arcs in the graph.

  # Define the directed graph for the flow.

  start_nodes = [0, 0, 0, 0] + [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4] + [5, 6, 7, 8]
  end_nodes =   [1, 2, 3, 4] + [5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8] + [9, 9, 9, 9]
  capacities =  [1, 1, 1, 1] + [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] + [1, 1, 1, 1 ]
  costs  = ([0, 0, 0, 0] + [90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115]
                + [0, 0, 0, 0])
  source = 0
  sink = 9
  tasks = 4
  supplies = [4, 0, 0, 0, 0, 0, 0, 0, 0, -4]

To make clear how the data is set up, each array is divided into three sub-arrays:

  • The first array corresponds to arcs leading out of the source.
  • The second array corresponds to the arcs between workers and tasks. For the costs, this is just the cost matrix (used by the linear assignment solver), flattened into a vector.
  • The third array corresponds to the arcs leading into the sink.

The data also includes the vector supplies, which gives the supply at each node.

How a min cost flow problem represents an assignment problem

How does the min cost flow problem above represent an assignment problem? First, since the capacity of every arc is 1, the supply of 4 at the source forces each of the four arcs leading into the workers to have a flow of 1.

Next, the flow-in-equals-flow-out condition forces the flow out of each worker to be 1. If possible, the solver would direct that flow across the minimum cost arc leading out of each worker. However, the solver cannot direct the flows from two different workers to a single task. If it did, there would be a combined flow of 2 at that task, which could not be sent across the single arc with capacity 1 from the task to the sink. This means that the solver can only assign a task to a single worker, as required by the assignment problem.

Finally, the flow-in-equals-flow-out condition forces each task to have an outflow of 1, so each task is performed by some worker.

Create the graph and constraints

The following code creates the graph and constraints.

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

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

Invoke the solver

The following code invokes the solver and displays the solution.

  if min_cost_flow.Solve() == min_cost_flow.OPTIMAL:
    print('Total cost = ', min_cost_flow.OptimalCost())
    print()
    for arc in range(min_cost_flow.NumArcs()):

      # Can ignore arcs leading out of source or into sink.
      if min_cost_flow.Tail(arc)!=source and min_cost_flow.Head(arc)!=sink:

        # Arcs in the solution have a flow value of 1. Their start and end nodes
        # give an assignment of worker to task.

        if min_cost_flow.Flow(arc) > 0:
          print('Worker %d assigned to task %d.  Cost = %d' % (
                min_cost_flow.Tail(arc),
                min_cost_flow.Head(arc),
                min_cost_flow.UnitCost(arc)))
  else:
    print('There was an issue with the min cost flow input.')
The solution consists of the arcs between workers and tasks that are assigned a flow of 1 by the solver. (Arcs connected to the source or sink are not part of the solution.) The program checks each arc to see if it has flow 1, and if so, prints the Tail (start node) and the Head (end node) of the arc, which correspond to a worker and task in the assignment.

Output of the program

Here is the output of the program.

Total cost = 265

Worker 1 assigned to task 8.  Cost = 70
Worker 2 assigned to task 7.  Cost = 55
Worker 3 assigned to task 6.  Cost = 95
Worker 4 assigned to task 5.  Cost = 45

Time = 0.000245 seconds
The result is the same as that for the linear assignment solver (except for the different numbering of workers and costs). The linear assignment solver is slightly faster than min cost flow — 0.000147 seconds versus 0.000458 seconds.

The entire program

The entire program is shown below.

from __future__ import print_function
from ortools.graph import pywrapgraph
import time

def main():
  """Solving an Assignment Problem with MinCostFlow"""

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

  # Define the directed graph for the flow.

  start_nodes = [0, 0, 0, 0] + [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4] + [5, 6, 7, 8]
  end_nodes =   [1, 2, 3, 4] + [5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8] + [9, 9, 9, 9]
  capacities =  [1, 1, 1, 1] + [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] + [1, 1, 1, 1 ]
  costs  = ([0, 0, 0, 0] + [90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115]
                + [0, 0, 0, 0])
  source = 0
  sink = 9
  tasks = 4
  supplies = [4, 0, 0, 0, 0, 0, 0, 0, 0, -4]

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

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

  # Find the minimum cost flow between node 0 and node 10.
  if min_cost_flow.Solve() == min_cost_flow.OPTIMAL:
    print('Total cost = ', min_cost_flow.OptimalCost())
    print()
    for arc in range(min_cost_flow.NumArcs()):

      # Can ignore arcs leading out of source or into sink.
      if min_cost_flow.Tail(arc)!=source and min_cost_flow.Head(arc)!=sink:

        # Arcs in the solution have a flow value of 1. Their start and end nodes
        # give an assignment of worker to task.

        if min_cost_flow.Flow(arc) > 0:
          print('Worker %d assigned to task %d.  Cost = %d' % (
                min_cost_flow.Tail(arc),
                min_cost_flow.Head(arc),
                min_cost_flow.UnitCost(arc)))
  else:
    print('There was an issue with the min cost flow input.')
if __name__ == '__main__':
  start_time = time.clock()
  main()
  print()
  print("Time =", time.clock() - start_time, "seconds")

Assignment with teams of workers

This section presents a more general assignment problem. In this problem, six workers are divided into two teams. The problem is to assign four tasks to the workers so that the workload is equally balanced between the teams — that is, so each team performs two of the tasks.

For a MIP solver solution to this problem see Assignment with Teams of Workers.

The following sections describe a Python program that solves the problem using the min cost flow solver.

Create the data and constraints

The following code creates the data and constraints for the program.

  # Define the directed graph for the flow.
  team_A = [1, 3, 5]
  team_B = [2, 4, 6]

  start_nodes = ([0, 0]  + [11, 11, 11] + [12, 12, 12] +
                 [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6] +
                 [7, 8, 9, 10])
  end_nodes =   ([11, 12] + team_A + team_B +
                 [7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10] +
                 [13, 13, 13, 13])
  capacities =  ([2, 2] + [1, 1, 1] + [1, 1, 1] +
                 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] +
                 [1, 1, 1, 1])
  costs      =  ([0, 0] + [0, 0, 0] + [0, 0, 0] +
                 [90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 60, 105,
                  80, 75, 45, 65, 110, 95] + [0, 0, 0, 0])

  # Define an array of supplies at each node.

  supplies = [4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -4]
  source = 0
  sink = 13

The workers correspond to nodes 1 - 6. Team A consists of workers 1, 3, and 5, and team B consists of workers 2, 4, and 6. The tasks are numbered 7 - 10.

There are two new nodes, 11 and 12, between the source and workers. Node 11 is connected to the nodes for team A, and Node 12 is connected to the nodes for team B, with arcs of capacity 1. The graph below shows just the nodes and arcs from the source to the workers.

Workers Source Capacity = 2 Capacity = 2 0 11 12 1 2 3 4 5 6

The key to balancing the workload is that the source 0 is connected to nodes 11 and 12 by arcs of capacity 2. This means that nodes 11 and 12 (and therefore teams A and B) can have a maximum flow of 2. As a result, each team can perform at most two of the tasks.

Output of the program

The following shows the output of the program.

Total cost = 250

Worker 1 assigned to task 9.  Cost =  75
Worker 2 assigned to task 7.  Cost =  35
Worker 5 assigned to task 10.  Cost =  75
Worker 6 assigned to task 8.  Cost =  65

Time = 0.00031 seconds

Team A is assigned tasks 9 and 10, while team B is assigned tasks 7 and 8.

Note that the min cost flow solver is faster for this problem than the MIP solver, which takes around 0.006 seconds.

The entire program

The entire program is shown below.

from __future__ import print_function
from ortools.graph import pywrapgraph
import time

def main():
  min_cost_flow = pywrapgraph.SimpleMinCostFlow()
  
  # Define the directed graph for the flow.
  team_A = [1, 3, 5]
  team_B = [2, 4, 6]

  start_nodes = ([0, 0]  + [11, 11, 11] + [12, 12, 12] +
                 [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6] +
                 [7, 8, 9, 10])
  end_nodes =   ([11, 12] + team_A + team_B +
                 [7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10] +
                 [13, 13, 13, 13])
  capacities =  ([2, 2] + [1, 1, 1] + [1, 1, 1] +
                 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] +
                 [1, 1, 1, 1])
  costs      =  ([0, 0] + [0, 0, 0] + [0, 0, 0] +
                 [90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 60, 105,
                  80, 75, 45, 65, 110, 95] + [0, 0, 0, 0])

  # Define an array of supplies at each node.

  supplies = [4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -4]
  source = 0
  sink = 13

  # Add each arc.
  for i in range(0, len(start_nodes)):
    min_cost_flow.AddArcWithCapacityAndUnitCost(start_nodes[i], end_nodes[i],
                                                capacities[i], 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 10.
  if min_cost_flow.Solve() == min_cost_flow.OPTIMAL:
    min_cost_flow.Solve()
    print('Total cost = ', min_cost_flow.OptimalCost())
    print()

    for arc in range(min_cost_flow.NumArcs()):

      # Can ignore arcs leading out of source or intermediate nodes, or into sink.
      if (min_cost_flow.Tail(arc)!=0 and min_cost_flow.Tail(arc)!=11 and min_cost_flow.Tail(arc)!=12
          and min_cost_flow.Head(arc)!=13):

        # Arcs in the solution will have a flow value of 1. There start and end nodes
        # give an assignment of worker to task.

        if min_cost_flow.Flow(arc) > 0:
          print('Worker %d assigned to task %d.  Cost = %d' % (
                min_cost_flow.Tail(arc),
                min_cost_flow.Head(arc),
                min_cost_flow.UnitCost(arc)))
  else:
    print('There was an issue with the min cost flow input.')
if __name__ == '__main__':
  start_time = time.clock()
  main()
  print()
  print("Time =", time.clock() - start_time, "seconds")