## Abstract

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 iid standard normal coefficients. In a special case of the MAP, a closed-form expression for E[M] is obtained when costs are iid 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.

Original language | English (US) |
---|---|

Pages (from-to) | 1-18 |

Number of pages | 18 |

Journal | Journal of Combinatorial Optimization |

Volume | 13 |

Issue number | 1 |

DOIs | |

State | Published - Jan 2007 |

Externally published | Yes |

## Keywords

- Combinatorial optimization
- Local minima
- Multidimensional assignment problem
- Neighborhood search
- Random costs

## ASJC Scopus subject areas

- Computer Science Applications
- Discrete Mathematics and Combinatorics
- Control and Optimization
- Computational Theory and Mathematics
- Applied Mathematics