Assignment problem

Assignment problem

The assignment problem is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics. It consists of finding a maximum weight matching in a weighted bipartite graph.

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 speaking of the "Assignment problem" without any additional qualification, then the "Linear assignment problem" is meant.

Algorithms and generalizations

The Hungarian algorithm is one of many algorithms that have been devised that solve the linear assignment problem within time bounded by a polynomial expression of the number of agents.

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 a linear program. While it is possible to solve any of these problems using the simplex algorithm, each specialization has more efficient algorithms designed to take advantage of its special structure. If the cost function involves quadratic inequalities it is called the quadratic assignment problem.

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 dummy 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 a bijection "f" : "A" → "T" such that the cost function:

::sum_{ain A}C(a,f(a)):is minimized.

Usually the weight function is viewed as a square real-valued matrix "C", so that the cost function is written down as:

:sum_{ain A}C_{a,f(a)}

The problem is "linear" because the cost function to be optimized as well as all the constraints contain only linear terms.

The problem can be expressed as a standard linear program with the objective function

:sum_{iin A}sum_{jin A}C(i,j)x_{ij}

subject to the constraints

:sum_{jin A}x_{ij}=1 for iin A,

:sum_{iin A}x_{ij}=1 for jin A,

:x_{ij}ge 0 for i,jin A.

The variable x_{ij} represents the assignment of agent i to task j, taking value 1 if the assignment is done and 0 otherwise. This formulation allows also fractional variable values, but there is always an optimal solution where the variables take integer values. This is because the constraint matrix is totally unimodular. The first constraint requires that every agent is assigned to exactly one task, and the second constraint requires that every task is assigned exactly one agent.

ee also

*Stable marriage problem
*auction algorithm


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Generalized assignment problem — In applied mathematics, the maximum general assignment problem is a problem in combinatorial optimization. This problem is a generalization of the assignment problem in which both tasks and agents have a size. Moreover, the size of each task… …   Wikipedia

  • Quadratic assignment problem — The quadratic assignment problem (QAP) is one of fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics, from the category of the facilities location problems.The problem models the… …   Wikipedia

  • Assignment — wiktionarypar|assignmentAssignment may refer to:* Assignment (computer science), modification of the value of a variable in a computer program * Assignment (education), required work to be completed outside the classroom * Assignment (law),… …   Wikipedia

  • Assignment Nor'Dyren — is a 1973 science fiction novel by Sydney J. Van Scyoc. This science fiction story can be viewed as an allegorical exploration of an important question regarding human society: why do some humans seem to put their energies into creative endeavors …   Wikipedia

  • Assignment (computer science) — In computer programming, an assignment statement sets or re sets the value stored in the storage location(s) denoted by a variable name. In most imperative computer programming languages, assignment statements are one of the basic statements.… …   Wikipedia

  • Route assignment — Route assignment, route choice, or traffic assignment concerns the selection of routes (alternative called paths) between origins and destinations in transportation networks. It is the fourth step in the conventional transportation forecasting… …   Wikipedia

  • Marriage problem — In mathematics, marriage problem can refer to: the assignment problem the secretary problem the stable marriage problem This disambiguation page lists articles associated with the same title. If an …   Wikipedia

  • Boolean satisfiability problem — For the concept in mathematical logic, see Satisfiability. 3SAT redirects here. For the Central European television network, see 3sat. In computer science, satisfiability (often written in all capitals or abbreviated SAT) is the problem of… …   Wikipedia

  • Independent set problem — In mathematics, the independent set problem (IS) is a well known problem in graph theory and combinatorics. The independent set problem is known to be NP complete. It is almost identical to the clique problem. Description Given a graph G , an… …   Wikipedia

  • Constraint satisfaction problem — Constraint satisfaction problems (CSP)s are mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”