Graph partitions for the multidimensional assignment problem

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 <Subscript> m×n </Subscript>, 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 n≥3 dimensions renders it <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\mathcal{NP}$</EquationSource> </InlineEquation>-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. Copyright Springer Science+Business Media New York 2014