An assignment problem is a type of problem in mathematics where the members of one set (referred to as agents) must be assigned to the members of another set (referred to as tasks) in such a way that each agent is assigned to exactly one task, each task has exactly one agent assigned to it, and the total cost of the assignment is minimized.
The cost of an assignment is determined from a cost function, which gives the cost of assigning a particular agent to a particular task. The overall cost of the assignment is then equal to the sum of the costs for each agent (or the sum of the costs for each task, which is the same thing).
For example, suppose that a taxi firm has three taxis (the agents) available, and three customers (the tasks) wishing to be picked up at the same time. Then for each taxi, the cost of picking up a particular customer will depend on how far the taxi must drive to reach the pickup point (or alternatively, if the firm prides itself on speedy pickups, on the time which the drive will take). The solution to the assignment problem will be whichever combination of taxis and customers results in the least total driving.
However, the assignment problem can be made rather more flexible than it at first appers. 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.
The assignment problem is a special case of another optimization problem known as the transportation problem, which in turn is a special case the maximal flow problem, which in turn is a special case of a linear program. While it is possible to solve all these problems using the simplex algorithm, each problem has more efficient algorithms designed to take advantage of their special structure. It is know that an algorithm exists to solve the assignment problem within time bounded by a polynomial expression of the number of agents.
A problem may be classified as an 'assignment problem' if the nature of the problem is such that there exist 2 sets of data, each with identical numbers of elements. Then there exists some function C, that provides the cost of assigning one of the 'A' elements, to one of the 'B' elements in a one-to-one manner.
As opposed to, for instance, a function D, which maps several elements of 'A' to a single element of 'B', or vice-versa; in which case one cannot say that this is an 'assignment problem'.
Mathematical Definition: An assignment problem (or "linear assignment") is any problem involving minimising the sum of C(a, b) over a set P of pairs (a, b) where a is an element of some set A and b is an element of set B, and C is some function, under constraints such as "each element of A must appear exactly once in P" or similarly for B, or both.
For example, the a's could be workers and the b's projects.
The problem is "linear" because the cost function to be optimized as well as all the constraints can be expressed as linear equations.
External Links
http://forum.swarthmore.edu/epigone/comp.soft-sys.matlab/bringhyclu
http://www.soci.swt.edu/capps/prob.htm
http://mat.gsia.cmu.edu/GROUP95/0577.html
http://www.informs.org/Conf/WA96/TALKS/SB24.3.html]
This article was originally based on material from FOLDOC, used with permission. Update as needed.