Local Neighborhoods for the Multidimensional Assignment Problem

Summary The Multidimensional Assignment Problem (MAP) is an extension of the two-dimensional assignment problem in which we find an optimal matching of elements between mutually exclusive sets. Although the two-dimensional assignment problem is solvable in polynomial time, extending the problem to three dimensions makes it $\mathcal {NP}$ -complete. The computational time to find an optimal solution of an MAP with at least three dimensions grows exponentially with the number of dimensions and factorially with the dimension size. Perhaps the most difficult implementation of the MAP is the data association problem that arises in multisensor multitarget tracking. We define new local search neighborhoods using the permutation formulation of the multidimensional assignment problem, where the feasible domain is defined by permutation vectors. Two types of neighborhoods are discussed, the intrapermutation and the interpermutation k-exchange. If the exchanges are restricted to elements within a single permutation vector, we classify the moves as intrapermutation. Interpermutation exchanges move elements from one permutation vector to another. Since combinatorial optimization heuristics tend to get trapped in local minima, we also discuss variable neighborhood implementations based on the new local search neighborhoods.