The multidimensional assignment problem (MAP) is a fundamental combinatorial optimization problem which was introduced by William Pierskalla.
[2] In words, the problem can be described as follows: Alternatively, describing the problem using graph theory: Various formulations of this problem can be found in the literature.
[4] The multidimensional assignment problem (MAP) has two key parameters that determine the size of a problem instance: Any problem instance of the MAP with parameters
is the size of cost array.
The feasible region or solution space of the MAP is very large.
of feasible solutions (the size of the MAP instance) depends on the MAP parameters
[2] The problem is generally NP-hard.
In other words, there is no known algorithm for solving this problem in polynomial time, and so a long computational time may be needed for solving problem instances of even moderate size (based on dimensionality and cardinality parameters).
[5] The problem found application in many domains: