Minimum Cost Assignment Problem Matrix

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.

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 , 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 (start node) and the (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.

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")

 

Assignment Problem

A typical assignment problem, presented in the classic manner, is shown in Fig. 12. Here there are five machines to be assigned to five jobs. The numbers in the matrix indicate the cost of doing each job with each machine. Jobs with costs of M are disallowed assignments. The problem is to find the minimum cost matching of machines to jobs.

Figure 12. Matrix model of the assignment problem.

The network model is in Fig. 13. It is very similar to the transportation model except the external flows are all +1 or -1. The only relevant parameter for the assignment model is arc cost (not shown in the figure for clarity) ; all other parameters should be set to default values. The assignment network also has the bipartite structure.

Figure 13. Network model of the assignment problem.

The solution to the assignment problem as shown in Fig. 14 has a total flow of 1 in every column and row, and is the assignment that minimizes total cost.

Figure 14. Solution to the assignment Problem

 

0 comments

Leave a Reply

Your email address will not be published. Required fields are marked *