Branch and bound solution of the multidimensional assignment problem formulation of data association

Abstract

The well-known index-based tree branch and bound algorithm for solution of the multidimensional assignment problem (MAP) is extended to handle multiple assignable 0-value indices, such as found in MAPs arising from the data association problem. Three different lower bounds for partial solutions are proposed and their effectiveness examined. Computational experiments are performed on instances of different size, different feasibility structure and sparseness, and different cost structure. It is shown how the use of a small range of integer weights commonly used in computational experiments on the solution of the MAP gives misleading results. The effects of different improvements of the basic algorithm are examined, including caching of feasibility tests, sorting of branches on each level of the tree, pruning of high cost branches, promotion of branches in the best known solution, and local search. Conclusions are that all of the proposed improvements reduce running times, especially sorting and pruning.

Keywords:

• multidimensional assignment problem
• data association problem
• branch and bound

AMS Subject Classification: :

• 65K05
• 90C08
• 90C57
• 90C90

Acknowledgements

The author would like to thank his colleague Henrik Holm for comments and suggestions leading to simplification of some of the proofs in Section 2.2.

Notes

Usually these costs will be negative log (pseudo) likelihood values or negative log-likelihood ratios from a probabilistic model.

Attempts to use the LPSolve function of Maple™ (v. 14, Maplesoft, Waterloo ON, Canada, 2010) on instances of size M=5 and N=5 in most cases yielded no result due to the inability of the LP sub-algorithm to find a feasible point.

The bintprog routine of MATLAB™ (R2011a, The MathWorks Inc., Natick MA, USA, 2011) fares better and will yield correct solutions, but the time required to solve most instances tested was several orders of magnitude larger than the time used by the specialized algorithm described in this paper.

CPLEX (IBM® ILOG® CPLEX® Optimization Studio 12.2, IBM Corp. 2010) is much faster than MATLAB and on the tried test instances require only about 7.4 times the computation time used by the specialized algorithm. An extensive comparison was not performed, however, and it is likely there are instance types for which an efficient LP-based branch and bound algorithm is faster than the index tree-based branch and bound algorithm described here.

For example, for an M=5, N=10 problem, even without 0-valued indices, having uniformly distributed integer random costs in the range 0 to 99 means the expected number of zero cost solutions will be over . If this was a problem corresponding to a DAP for a cluster of 10 trees observed in 5 aerial views, there would in most cases be only one most likely solution, even if the real-valued log (pseudo) likelihood costs were to be quantized to 10 bit integers (which, it could be argued, would be reasonable considering the noisy observations).