METHOD AND SYSTEM FOR TRACKING MULTIPLE OBJECTS

An improved method and system for solving a combinatorial optimization problem, such as a tracking problem, to define a plurality of associations of measurements taken of a plurality of objects is provided. In one aspect, a method, a system and a computer program product are provided for constructing a plurality of updated tracks by solving a Lagrangian dual in which each of the measurement constraints has been relaxed. In another aspect, a hybrid branch and bound and LR technique is provided to select a plurality of updated tracks from among a plurality of candidate tracks having respective initial costs. In this regard, a search tree of the candidate tracks is ordered based upon the initial costs of the candidate tracks as adjusted by the dual variables that have been defined as a result of solving a Lagrangian dual. In order to attempt to increase the efficiency with which a Lagrangian dual is solved by nonsmooth optimization techniques, initial values for the dual variables and some of the subgradients are judiciously selected. The dual variables are initialized and some subgradients are provided based upon values of corresponding dual variables and some of the subgradients, respectively, that were determined during the solution of the prior problem. The method and system can be implemented in a parallel processing architecture that utilizes both coarse grain and fine grain techniques to evenly schedule a number of subproblems amongst a plurality of processors in order to obtain a solution in an efficient manner.