Assignment as a Min Cost Flow Problem

Overview

The previous section showed how to solve an assignment problem with the linear assignment solver. This section shows how to solve the same problem with the more general minimum cost flow solver. While linear assignment is faster than min cost flow for this particular problem, min cost flow can solve a larger class of problems. Typically, a solver designed for a special class of problems will solve those problems faster than a solver that can handle a more general class of problems.

The following sections present a Python program that solves the assignment problem using min cost flow.

Create the solver

The following code creates the minimum cost flow solver.

from ortools.graph import pywrapgraph
import time

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

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

Create the data

The flow diagram for the problem is the bipartite graph from the problem with the previous section, 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 different from that of original example, 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])

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, flattened into a vector.
  • The third array corresponds to the arcs leading into the sink.

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

  supplies = [4, 0, 0, 0, 0, 0, 0, 0, 0, -4]

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 — which might be a consideration for a much larger assignment problem.

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])
  # Define an array of supplies at each node.
  supplies = [4, 0, 0, 0, 0, 0, 0, 0, 0, -4]
  source = 0
  sink = 9
  tasks = 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")

Balance the workload between two groups of workers

This section presents a more general assignment problem, which can't be solved by the linear assignment solver. 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.

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.

The entire program

The entire program is shown below.

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

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

  # Instantiate a SimpleMinCostFlow solver.
  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")

Send feedback about...

Optimization
Optimization