Multidimensional assignment problem


The multidimensional assignment problem 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:
Alternatively, describing the problem using graph theory:

Formal definition

Various formulations of this problem can be found in the literature. Using cost-functions, the dimensional assignment problem can be stated as follows:
is minimized.

Problem parameters

The multidimensional assignment problem has two key parameters that determine the size of a problem instance:
  1. The dimensionality parameter
  2. The cardinality parameter, where denotes the number of elements in.

Size of cost array

Any problem instance of the MAP with parameters has its specific cost array, which consists of instance-specific costs/weights parameters. is the size of cost array.

Number of feasible solutions

The feasible region or solution space of the MAP is very large. The number of feasible solutions depends on the MAP parameters . Specifically,.

Computational complexity

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.

Applications

The problem found application in many domains: