.png){kind=icon}
.png){kind=icon}
Return
Integer programming models for the multidimensional assignment problem with star costs
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ejor.2013.10.048.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We consider a variant of the multidimensional assignment problem (MAP) with decomposable costs in which the resulting optimal assignment is described as a set of disjoint stars. This problem arises in the context of multi-sensor multi-target tracking problems, where a set of measurements, obtained from a collection of sensors, must be associated to a set of different targets. To solve this problem we study two different formulations. First, we introduce a continuous nonlinear program and its linearization, along with additional valid inequalities that improve the lower bounds. Second, we state the standard MAP formulation as a set partitioning problem, and solve it via branch and price. These approaches were put to test by solving instances ranging from tripartite to 20-partite graphs of 4 to 30 nodes per partition. Computational results show that our approaches are a viable option to solve this problem. A comparative study is presented. (C) 2013 Elsevier B.V. All rights reserved.
Keywords:
Combinatorial optimization
Multidimensional assignment problem
Star covering
Multi-sensor multi-target tracking problem
Graph partitioning
Branch and price
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W
