Lecture
The assignment problem is one of the fundamental problems of combinatorial optimization in the field of mathematical optimization or operations research. The problem consists of finding the minimum sum of arcs in a weighted bipartite graph.
In its most general form the problem is formulated as follows:
There is a certain number of jobs and a certain number of workers. Any worker can be assigned to perform any (but only one) job, but at unequal cost. It is required to distribute the jobs so as to perform the jobs at minimal cost.
If the number of jobs and workers is equal, the problem is called the linear assignment problem. Usually, when one speaks of the assignment problem without further qualification, the linear assignment problem is meant.
In its most general form the problem looks as follows:
An instance of the problem has a number of agents and a number of tasks. Any agent may be assigned to perform any task, which requires a certain cost, which may vary depending on the assignment of the task to the agent. It is required to perform as many tasks as possible, assigning no more than one agent to each task and no more than one task to each agent, so that the total cost of the assignment is minimal.
A worked example of assigning tasks to an unequal number of workers using the Hungarian method
Alternatively, describing the problem using graph theory:
The assignment problem consists of finding, in a weighted bipartite graph, a matching of a given size in which the sum of the edge weights is minimal.
If the number of agents and tasks is equal, the problem is called a balanced assignment. Otherwise it is called an unbalanced assignment. If the total cost of the assignment across all tasks equals the sum of the costs for each agent (or the sum of the costs for each task, which in this case is the same thing), the problem is called a linear assignment. Usually, when one speaks of the assignment problem without any further clarification, the linear balanced assignment problem is meant.
The Hungarian algorithm is one of many algorithms developed for solving the linear assignment problem in time polynomial in the number of jobs.
The assignment problem is a special case of the transportation problem, which is a special case of the minimum-cost flow problem, which, in turn, is a special case of the linear programming problem. Any of these problems can be solved by the simplex method, but each specialization has its own more efficient algorithm relying on the specific structure of the problem.
If the objective function is expressed in terms of squares, one speaks of the quadratic assignment problem.
Suppose a taxi company has three free cars (workers) and three customers (jobs) who want to get a taxi as quickly as possible. The firm cares about the delivery time of the taxi to the customer, so for each car the cost is determined by the time it takes the car to reach the waiting location specified by the customer. The solution of the assignment problem will be a distribution of cars to customers such that the total cost (total waiting time) is minimal.
The assignment problem can be made more flexible. In the example above there might be not three but four free taxis, while the number of customers remains three. A fourth, dummy customer with zero cost can be assigned, and assigning a car to the dummy customer means «do nothing».
A similar technique can be used when the number of orders may exceed the number of available cars, and a car may be assigned to perform several jobs, and also when a job may be assigned to several workers (for example, if the customer is a group that does not fit in one taxi). One can also pose the problem of maximizing revenue rather than minimizing cost.
Formal statement of the assignment problem:
Given two sets A and T of the same size and a cost function C : A × T → R.
It is necessary to find a bijection f : A → T such that the objective function:
is minimal.
Usually the cost function is given as a square matrix C consisting of real numbers, so that the objective function can be written as:
The problem is called «linear» because both the objective function and the constraints contain only linear expressions.
The problem can be represented as a linear programming problem with the objective function
and constraints
for 
,
for 
,
for 
.
The variable 
represents the assignment of worker 
to job 
, taking the value 1 if the worker is assigned to that job and 0 otherwise. In this formulation the solution may not be integral, but an optimal integer-valued solution always exists. This fact follows from the total unimodularity of the matrix. The first constraint requires that exactly one task be assigned to each worker, the second requires that exactly one worker be assigned to each task.
There are other approaches to the assignment problem, which were considered by Duan and Pettie (see Table II). Their work presents an approximation algorithm for the problem (and the more general high-weight problem), which scales in linear time for any fixed error bound.
Generalization
In the graph-theoretic formulation of the problem, the assignment problem can be extended from bipartite graphs to general graphs. The corresponding problem of finding a matching of maximum weight sum in a weighted graph is called the maximum weight matching problem.
Another generalization of the assignment problem is increasing the number of matched sets from two to many. Thus, instead of agents matched with tasks, the problem is extended to adjustable agents with tasks, time slots, and positions. This leads to the multidimensional assignment problem (MAP).
Comments