A map-reduce lagrangian heuristic for multidimensional assignment problems with decomposable costs

Data association is the problem of identifying when multiple data sources have observed the same entity. Central to this effort is the multidimensional assignment problem, which is often used to formulate data association problems. The nature of data association problems dictate that solution methods for the multidimensional assignment problem must return results promptly, and work on large data sets. The contribution of this work is to describe a Lagrangian relaxation based heuristic for the multi-dimensional assignment problem with decomposable costs that can be largely implemented in a map-reduce framework and thus easily distributed across a cluster of computers. Distribution allows the heuristic to address run time and large data requirements of data association. The developed algorithm is tested on a synthesized dataset, and shown to achieve an optimality gap ranging from 0.00008% to 0.6% for dense (no filtering) problems having 10,000 observation. Distribution of the algorithm was found to offer a significant reduction in run time on 30,000 observation problems for an 8 node computing cluster with 96 processors over a single node with 12 processors.