On the number of local minima for the multidimensional assignment problem

The Multidimensional Assignment Problem (MAP) is an NP-hard combinatorial optimization problem occurring in many applications, such as data association, target tracking, and resource planning. As many solution approaches to this problem rely, at least partly, on local neighborhood search algorithms, the number of local minima affects solution difficulty for these algorithms. This paper investigates the expected number of local minima in randomly generated instances of the MAP. Lower and upper bounds are developed for the expected number of local minima, E[M], in an MAP with independent identically distributed standard normal coefficients. In a special case of the MAP, a closed-form expression for E[M] is obtained when costs are independent identically distributed continuous random variables. These results imply that the expected number of local minima is exponential in the number of dimensions of the MAP. Our numerical experiments indicate that larger numbers of local minima have a statistically significant negative effect on the quality of solutions produced by several heuristic algorithms that involve local neighborhood search.