The Assignment Problem: Optimally assigning agents to jobs. Credits: http://www.hungarianalgorithm.com/

The Assignment Problem (Using Hungarian Algorithm)

Ever encountered a problem where you wanted to divide work among people such that you do it in the most optimal way? Then this problem is just for you. The assignment problem assigns tasks to agents in the most optimal way! Read on ahead to know about the Assignment Problem and how to solve it using the “Hungarian Algorithm”.

What is the Assignment Problem?

Let there be n agents and n tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform all tasks by assigning exactly one agent to each task and exactly one task to each agent in such a way that the total cost of the assignment is minimized.
We need to ensure the following things:

1. The number of assignments and agents should be the same.
2. Each agent should be assigned only one job and every job should be assigned only one agent
3. We want to find the feasible solution which will consume the minimum cost

Example

Problem: In a construction site there are 4 cranes. Each crane must be allocated to one job. The time required for each job for each crane is shown in the table below. Find the best assignment of cranes to the jobs so that the time required to finish the jobs is minimum.

The highlighted boxes show the most optimal assignment.

Applications of the Assignment Problem

Few applications of the Assignment Problem are:

1. Assigning machines to factory orders.
2. Assigning sales/marketing people to territories.
3. Assigning teachers to classes.
4. Assigning police vehicles to patrolling areas.

Few Approaches to solve the Assignment Problem

Complexity Analysis for Brute force approach

• Approach 1: Brute Force
  Here we try all the combinations one by one to find the optimal solution. This is a tedious approach because as the number of tasks and cranes go on increasing , the number of calculations also increase. The complexity is n! which is very inefficient.
• Approach 2: Graph Approach
  The algorithm is easier to describe if we formulate the problem using a bipartite graph. We have a complete bipartite graph G=(S, T; E) with n worker vertices S and n job vertices (T), and each edge has a nonnegative cost c(i,j). We want to find a perfect matching with a minimum total cost.

Total Cost= 2+8+4+6=20

• Approach 3: Greedy Approach
  In this case, the algorithm will choose the lowest cost worker to be assigned to the task as the first assignment, then choose the next lowest cost worker to be assigned to the task, and so on until all tasks have been assigned. The algorithm repeats this procedure until all workers have at least one task. Greedy algorithms try to get close to the optimal solution by improving a candidate solution iteratively, with no guarantee that an optimal solution will actually be found.
• Approach 4: Hungarian Algorithm
  The Hungarian Algorithm is a combinatorial optimization algorithm which is a faster approach which solves the problem in polynomial time complexity. We see the Hungarian approach ahead.

The Hungarian Algorithm

1.Find the minimum element from each row and substract that value from all the elements of the row.

2. Find the minimum element from each column and substract that value from all the elements of the column.

3. Let m=minimum number of lines required to cover all the zeroes in the table

4. while(m!=number of row/columns)

• Find the minimum element from the uncovered elements
• Substract this element from all the other uncovered elements
• Add this element to the elements where the lines are intersecting
• Find new m

5. Use the zeroes to assign possible combinations- i.e wherever there is a zero present, task can be assigned.

6. Find the minimum cost

7. End

Solving an Example Using Hungarian Problem

We use the previous problem statement (in the example mentioned above) and solve that problem using Hungarian Algorithm.

STEP 1: Finding the minimum from each row and substracting it from all the other row elements

In the table 1 the minimum elements from each row are highlighted. Table 2 shows the new table after substracting.

STEP 2: Finding the minimum from each column and substracting it from all the other column elements

The Table 1 shows the minimum in each column and the table 2 shows the substracted values.

STEP 3: Finding the minimum number of lines required to cover all the zeroes

Table with lines

As we can see that when we draw lines on column 1 and 2 and row 3, all the zeroes of the table are covered but this is not equal to the number of rows and columns.

STEP 4.i.ii.iii: Finding the minimum element from the uncovered elements and substract it from the rest of the uncovered elements and adding it to the intersecting elements.

Here 3 is the minimum element so we substract it from the uncovered elements and add it to the intersecting elements(circled in blue).

Step 4.iv. Finding the minimum number of lines required to cover all the zeroes.

Table with minimum number of lines covering the elements

Now we see that upon drawing the lines on Row 1, Row 2 and Column 2, all the zeroes are covered. But still the number of lines(m) is not equal to the number of rows/columns(n) and so we repeat step 4 again.

Step 4.i.ii.iii. Finding the minimum from the uncovered elements, substracting it from the rest of the uncovered elements and adding that element to the elements where lines are intersecting.

In table 1 we see that the minimum element from the uncovered elements is 1, so we substract that from rest of the uncovered elements and add it to the intersecting elements(circled in blue). Table 2 shows the calculated values.

Step 4.iv. Finding the minimum number of lines required to cover all the zeroes.

Now we see that on drawing vertical lines on row 1, row 2, row 3, row 4 we have covered all the zeroes in minimum number of lines. Now our number of lines(m)=number of rows/columns(n)=4 and so we have reached an optimal solution.

Step 5: Use the zeroes to assign possible combinations- wherever there is a zero present, task can be assigned to respective agent and job.

We assign the tasks such that in every row and column there is only one task assigned. The boxes in purple indicate the assigned tasks. We then use these assignments in the original cost table (table 2).

Step 6: Find the cost.

Costs calculated using the previous table assignment.

When we use the previous tables assignments of the jobs and cranes, we calculate the cost by adding the costs of the individual assignment. The minimum cost comes out to be 19 which tallies with the solution we got in the previous example. Hence we have arrived at the solution.

Note: If we assume the other combinations, we will still get the same answer of minimum value. The other combinations using the zeroes in the table obtained in 4(iv) gives us the same minimum cost.

Total Cost for table 1= 5+3+5+6=19 and total cost for table 2=4+8+4+3=19

Hope after reading this blog your concepts about the Assignment Problem and Hungarian Algorithm are clear!

Credits: The example used in this blog has been taken from the following YouTube video — https://www.youtube.com/watch?v=ezSx8OyBZVc. The problem statement is taken from — https://www.geeksforgeeks.org/hungarian-algorithm-assignment-problem-set-1-introduction/