In this paper, we consider two decomposition schemes for the graph theoretical description of the axial multidimensional Assignment problem (MAP). The problem is defined as finding n disjoint cliques of size m with mi...
详细信息
In this paper, we consider two decomposition schemes for the graph theoretical description of the axial multidimensional Assignment problem (MAP). The problem is defined as finding n disjoint cliques of size m with minimum total cost in K (mxn) , which is an m-partite graph with n elements per dimension. Even though the 2-dimensional assignment problem is solvable in polynomial time, extending the problem to include na parts per thousand yen3 dimensions renders it -hard. We propose two novel decomposition schemes for partitioning a MAP into disjoint subproblems, that can then be recombined to provide both upper and lower bounds to the original problem. For each of the partitioning schemes, we investigate and compare the efficiency of distinct exact and heuristic methodologies, namely augmentation and partitioning. Computational results for the methods, along with a hybrid one that consists of both partitioning schemes, are presented to depict the success of our approaches on large-scale instances.
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 m...
详细信息
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.
暂无评论