Assignment problem: Difference between revisions

Revision as of 15:00, 28 September 2003

Revision as of 01:37, 25 October 2003

Line 1:

An '''assignment problem''' is an important problem in the branch of [[optimization]] or [[operations research]] in [[mathematics]]. The problem is as follows:

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 of equal size (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.

:There are a number of ''agents'' and an equal number of ''tasks'', we want to search a way to assign each agent exactly one task such that the total ''cost'' of the assignment is minimized.

The assignment problem is a special case of another optimization problem known as the [[transportation problem]], which 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 any of these problems using the [[simplex algorithm]], each problem has more efficient algorithms designed to take advantage of its 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.

The requirement about equal number of agents and tasks could be relaxed, as shown in the example below.

==An example==

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).

Line 5 ⟶ 13:

For 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 at first appersappears. 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 assignment problem is a special case of another optimization problem known as the [[transportation problem]], which 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 any of these problems using the [[simplex algorithm]], each problem has more efficient algorithms designed to take advantage of its 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.

'''Formal mathematical definition'''

AnThe formal definition of an '''assignment problem''' (or '''linear assignment''') gives two sets, ''A'' and ''T'', of equal size, together with a cost function ''C'' which maps pairs (''a'',''t'') (where ''a'' lies in ''A'' and ''t'' in ''T'') to [[real number]]s.is

The:Given problemtwo thensets, is''A'' toand ''T'', of equal size, together with a cost function ''C'':''A''×''T''→'''[[real number|R]]'''. findFind the [[bijection]] ''f'' from :''A'' to →''T'' such that the sum of Σ_{''Ca''(∈''aA'',}''fC''(''a'')) across all ,''af'' in (''Aa'')) is minimized.

The problem is "linear" because the cost function to be optimized as well as all the constraints can be expressed as linear equations.