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:
-
- 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 contain only linear terms.
The problem can be expressed as a standard linear program with the objective function
subject to the constraints
The variable represents the assignment of agent to task, 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.
Read more about this topic: Assignment Problem
Famous quotes containing the words formal, mathematical and/or definition:
“On every formal visit a child ought to be of the party, by way of provision for discourse.”
—Jane Austen (1775–1817)
“All science requires mathematics. The knowledge of mathematical things is almost innate in us.... This is the easiest of sciences, a fact which is obvious in that no one’s brain rejects it; for laymen and people who are utterly illiterate know how to count and reckon.”
—Roger Bacon (c. 1214–c. 1294)
“Although there is no universal agreement as to a definition of life, its biological manifestations are generally considered to be organization, metabolism, growth, irritability, adaptation, and reproduction.”
—The Columbia Encyclopedia, Fifth Edition, the first sentence of the article on “life” (based on wording in the First Edition, 1935)