assignment problem solver python

• Google OR-Tools
• Español – América Latina
• Português – Brasil
• Tiếng Việt

Linear Sum Assignment Solver

This section describes the linear sum assignment solver , a specialized solver for the simple assignment problem, which can be faster than either the MIP or CP-SAT solver. However, the MIP and CP-SAT solvers can handle a much wider array of problems, so in most cases they are the best option.

Cost matrix

The costs for workers and task are given in the table below.

The following sections present a Python program that solves an assignment problem using the linear sum assignment solver.

Import the libraries

The code that imports the required library is shown below.

Define the data

The following code creates the data for the program.

The array is the cost matrix , whose i , j entry is the cost for worker i to perform task j . There are four workers, corresponding to the rows of the matrix, and four tasks, corresponding to the columns.

Create the solver

The program uses the linear assignment solver, a specialized solver for the assignment problem.

The following code creates the solver.

Add the constraints

The following code adds the costs to the solver by looping over workers and tasks.

Invoke the solver

The following code invokes the solver.

Display the results

The following code displays the solution.

The output below shows the optimal assignment of workers to tasks.

The following graph shows the solution as the dashed edges in the graph. The numbers next to the dashed edges are their costs. The total wait time of this assignment is the sum of the costs for the dashed edges, which is 265.

In graph theory, a set of edges in a bipartite graph that matches every node on the left with exactly one node on the right is called a perfect matching .

The entire program

Here is the entire program.

Solution when workers can't perform all tasks

In the previous example, we assumed that all workers can perform all tasks. But this not always the case - a worker might be unable to perform one or more tasks for various reasons. However, it is easy to modify the program above to handle this.

As an example, suppose that worker 0 is unable to perform task 3. To modify the program to take this into account, make the following changes:

• Change the 0, 3 entry of the cost matrix to the string 'NA' . (Any string will work.) cost = [[90, 76, 75, 'NA'], [35, 85, 55, 65], [125, 95, 90, 105], [45, 110, 95, 115]]
• In the section of the code that assigns costs to the solver, add the line if cost[worker][task] != 'NA': , as shown below. for worker in range(0, rows): for task in range(0, cols): if cost[worker][task] != 'NA': assignment.AddArcWithCost(worker, task, cost[worker][task]) The added line prevents any edge whose entry in the cost matrix is 'NA' from being added to the solver.

After making these changes and running the modified code, you see the following output:

Notice that the total cost is higher now than it was for the original problem. This is not surprising, since in the original problem the optimal solution assigned worker 0 to task 3, while in the modified problem that assignment is not allowed.

To see what happens if more workers are unable to perform tasks, you can replace more entries of the cost matrix with 'NA' , to denote additional workers who can't perform certain tasks:

When you run the program this time, you get a negative result:

This means there is no way to assign workers to tasks so that each worker performs a different task. You can see why this is so by looking at the graph for the problem (in which there are no edges corresponding to values of 'NA' in the cost matrix).

Since the nodes for the three workers 0, 1, and 2 are only connected to the two nodes for tasks 0 and 1, it not possible to assign distinct tasks to these workers.

The Marriage Theorem

There is a well-known result in graph theory, called The Marriage Theorem , which tells us exactly when you can assign each node on the left to a distinct node on the right, in a bipartite graph like the one above. Such an assignment is called a perfect matching . In a nutshell, the theorem says this is possible if there is no subset of nodes on the left (like the one in the previous example ) whose edges lead to a smaller set of nodes on the right.

More precisely, the theorem says that a bipartite graph has a perfect matching if and only if for any subset S of the nodes on the left side of the graph, the set of nodes on the right side of the graph that are connected by an edge to a node in S is at least as large as S.

Except as otherwise noted, the content of this page is licensed under the Creative Commons Attribution 4.0 License , and code samples are licensed under the Apache 2.0 License . For details, see the Google Developers Site Policies . Java is a registered trademark of Oracle and/or its affiliates.

Last updated 2023-01-18 UTC.