Local Neighborhoods for the Multidimensional Assignment Problem

Eduardo L. Pasiliao ()
Additional contact information
Eduardo L. Pasiliao: AFRL Munitions Directorate

Chapter Chapter 19 in Dynamics of Information Systems, 2010, pp 353-371 from Springer

Abstract: 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.

Keywords: Local Search; Assignment Problem; Local Neighborhood; Variable Neighborhood; Variable Neighborhood Search (search for similar items in EconPapers)
Date: 2010
References: Add references at CitEc
Citations: View citations in EconPapers (3)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-1-4419-5689-7_19

Ordering information: This item can be ordered from
http://www.springer.com/9781441956897

DOI: 10.1007/978-1-4419-5689-7_19

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().