Multidimensional assignment problem
The multidimensional assignment problem (MAP) is a fundamental combinatorial optimization problem which was introduced by William Pierskalla.
≈ 4 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
The multidimensional assignment problem (MAP) is a fundamental combinatorial optimization problem which was introduced by William Pierskalla. This problem can be seen as a generalization of the linear assignment problem.
In words, the problem can be described as follows: : An instance of the problem has a number of agents (i.e., cardinality parameter) and a number of job characteristics (i.e., dimensionality parameter) such as task, machine, time interval, etc. For example, an agent can be assigned to perform task X, on machine Y, during time interval Z. Any agent can be assigned to perform a job with any combination of unique job characteristics at some cost. These costs may vary based on the assignment of agent to a combination of job characteristics - specific task, machine, time interval, etc. The problem is to minimize the total cost of assigning the agents so that the assignment of agents to each job characteristic is an injective function, or one-to-one function from agents to a given job characteristic.
Alternatively, describing the problem using graph theory: :The multidimensional assignment problem consists of finding, in a weighted multipartite graph, a matching of a given size, in which the sum of weights of the edges is minimum.
The multidimensional assignment problem (MAP) is a fundamental combinatorial optimization problem which was introduced by William Pierskalla. This problem can be seen as a generalization of the linear assignment problem.
In words, the problem can be described as follows: An instance of the problem has a number of agents (i.e., cardinality parameter) and a number of job characteristics (i.e., dimensionality parameter) such as task, machine, time interval, etc. For example, an agent can be assigned to perform task X, on machine Y, during time interval Z. Any agent can be assigned to perform a job with any combination of unique job characteristics at some cost. These costs may vary based on the assignment of agent to a combination of job characteristics - specific task, machine, time interval, etc. The problem is to minimize the total cost of assigning the agents so that the assignment of agents to each job characteristic is an injective function, or one-to-one function from agents to a given job characteristic.
Alternatively, describing the problem using graph theory: The multidimensional assignment problem consists of finding, in a weighted multipartite graph, a matching of a given size, in which the sum of weights of the edges is minimum.
Formal definition
Various formulations of this problem can be found in the literature. Using cost-functions, the D dimensional assignment problem (or D MAP) can be stated as follows: Given D sets, A and J_1, \ldots J_{D-1} , of equal size, together with a cost array or multidimensional weight function C : A \times J_1 \times \ldots \times J_{D-1} \rightarrow \mathbb{R}_+ , find D-1 permutations \pi_{d} : A → J_d such that the total cost function: \sum_{a\in A}C(a,\pi_{1}(a),\ldots,\pi_{D-1}(a)) is minimized.
The cardinality parameter N = |A| , where |A| denotes the number of elements in A . The feasible region or solution space of the MAP is very large. The number K of feasible solutions (the size of the MAP instance) depends on the MAP parameters D, N . Specifically, K = (N!)^{D-1} .
Text derived from https://en.wikipedia.org/w/index.php?oldid=1359732822 under CC BY-SA 4.0; modifications have been made.