The assignment problem is one of fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics.
In its most general form, the problem is as follows:
- There are a number of agents and a number of 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 in such a way that the total cost of the assignment is minimized.
If the numbers of agents and tasks are equal and the total cost of the assignment for all tasks is equal to the sum of the costs for each agent (or the sum of the costs for each task, which is the same thing in this case), then the problem is called the Linear assignment problem. Commonly, when spoking of the Assignment problem without any additional qualification, then the Linear assignment problem is meant.
Other kinds are the quadratic assignment problem, bottleneck assignment problem.
The assignment problem is a special case of another optimization problem known as the transportation problem, which is a special case of the maximal flow problem, which in turn is a special case of a linear program. While it is possible to solve any of these problems using the simplex algorithm, each problem has more efficient algorithms designed to take advantage of its special structure. Algorithms have been devised that solve the linear assignment problem within time bounded by a polynomial expression of the number of agents.
The restrictions on agents, tasks and cost in the (linear) assignment problem could be relaxed, as shown in the example below.
Example
Suppose that a taxi firm has three taxis (the agents) available, and three customers (the tasks) wishing to be picked up as soon as possible. The firm prides itself on speedy pickups, so for each taxi the "cost" of picking up a particular customer will depend on the time taken for the taxi to reach the pickup point. The solution to the assignment problem will be whichever combination of taxis and customers results in the least total cost.
However, the assignment problem can be made rather more flexible than it first appears. In the above example, suppose that there are four taxis available, but still only three customers. Then a fourth task can be invented, perhaps called "sitting still doing nothing", with a cost of 0 for the taxi assigned to it. The assignment problem can then be solved in the usual way and still give the best solution to the problem.
Similar tricks can be played in order to allow more tasks than agents, tasks to which multiple agents must be assigned (for instance, a group of more customers than will fit in one taxi), or maximizing profit rather than minimizing cost.
Formal mathematical definition
The formal definition of the assignment problem (or linear assignment problem) is
- Given two sets, A and T, of equal size, together with a weight function C : A × T → R. Find the bijection f : A → T such that the cost function:
- is minimized.
Usually the weight function is viewed as a square real-valued matrix C, so that the cost function is written down as:
The problem is "linear" because the cost function to be optimized as well as all the constraints can be expressed as linear equations.
Solving an assignment problem
Assignment problems are generally easy to solve since there exists a one to one correspondence.
First the problem is written in the form of a matrix as given below
Where a,b,c and d are the agents who have to perform tasks 1,2,3 and 4. a1,a2,a3,a4 denote the penalties incurred when a does task 1,2,3,4 respectively. Same hold true for the other symbols as well. Note that the matrix is a square matrix[this has to be so since each agent can perform only one task].
Then we perform row operations on the matrix. To do this, the lowest of all ai [i belonging to 1-4] is taken and is subtracted from the other elements in that row. This will lead to at least one zero in that row [We get multiple zeros when there are two equal elements which also happen to be the lowest in that row]. This procedure is repeated for all rows. We now have a matrix with at least one zero per row. Now we try to assign tasks to agents such that each agent is doing only one task and the penalty incurred in each case is zero. This is illustrated below.
Note-Matrix notation hasnt been used since formatting is not possible with that
0 a2' 0' a4'
b1' b2' b3' 0'
0' c2' c3' c4'
d1' 0' d3' d4'
The zeros that are indicated as 0' are the assigned tasks.
In some cases it may turn out that the above matrix cannot be used for assigning.
0 a2' a3' a4'
b1' b2' b3' 0
0 c2' c3' c4'
d1' 0 d3' d4'
In the above case no assignment can be made. Note that task 1 is done efficiently by both agent a and c. Both cant be assigned the same task. Also note that no one does task 3 efficiently. To overcome this, we repeat the above procedure for all columns and then check if an assignment is possible. In most situations this will lead the result, but if it is still not possible to assign then the procedure described below must be followed.
Initially assign as many tasks as possible then do the following[assign tasks in rows 2,3 and 4]-
0 a2' a3' a4'
b1' b2' b3' 0'
0' c2' c3' c4'
d1' 0' d3' d4'
Mark all rows having no assignments [row 1]. Then mark all columns having zeros in that row [column 1]. Then mark all rows having assignments in the given column [row 3]. Then mark all columns having assignments in the given rows. Repeat this till a closed loop is obtained.
×
0 a2' a3' a4' ×
b1' b2' b3' 0'
0' c2' c3' c4' ×
d1' 0' d3' d4'
Now draw lines through all marked columns and unmarked rows.
0 a2' a3' a4'
b1' b2' b3' 0'
0' c2' c3' c4'
d1' 0' d3' d4'
Note-Since a verticle line cannot be drawn a horizontal line is used to cut the 1st column.
From the elements that are left, find the lowest value. Subtract this from all elements that are not struck. Add this to elements that are present at the intersection of two lines. Leave other elements unchanged. Now assign the tasks using above rules. Repeat the procedure till an assignment is possible.