A new Lagrangian relaxation based algorithm for a class of multidimensional assignment problems

Large classes of data association problems in multiple target tracking applications involving both multiple and single sensor systems can be formulated as multidimensional assignment problems. These NP-hard problems are large scale and sparse with noisy objective function values, but must be solved in ‘real-time’. Lagrangian relaxation methods have proven to be particularly effective in solving these problems to the noise level in real-time, especially for dense scenarios and for multiple scans of data from multiple sensors. This work presents a new class of constructive Lagrangian relaxation algorithms that circumvent some of the deficiences of previous methods. The results of several numerical studies demonstrate the efficiency and effectiveness of the new algorithm class.