Title: Sequential constraint augmentation with variable neighbourhood search for the multidimensional assignment problem

Authors: Eduardo L. Pasiliao, Panos M. Pardalos

Addresses: Air Force Research Laboratory, 101 West Eglin Boulevard, Eglin AFB FL 32542-5427, USA. ' Department of Industrial and Systems Engineering, University of Florida, 303 Weil Hall, Gainesville FL 32611-6595, USA

Abstract: This work proposes the Sequential Constraint Augmentation (SCA) procedure for the Multidimensional Assignment Problem (MAP). Although the two-dimensional assignment problem has been shown to be solvable in polynomial time, the problem becomes NP-hard when it is extended to three dimensions. We investigate the benefits of implementing an intra-permutation 2 exchange and variable neighbourhood search for the SCA. The variable neighbourhood approach utilises the intra-permutation 2 and n-exchanges and the inter permutation 2-exchange. All three κ-exchange neighbourhoods are motivated by the permutation formulation of the MAP. Computational results show that the SCA procedure provides a tight upper bound with little computational effort. Exploring our variable neighbourhood significantly improves the SCA solution within a relatively short amount of computation time.

Keywords: multidimensional assignment problem; combinatorial optimisation; computational results; sequential constraint augmentation; neighbourhood search.

DOI: 10.1504/IJCSE.2007.017824

International Journal of Computational Science and Engineering, 2007 Vol.3 No.3, pp.184 - 193

Published online: 18 Apr 2008 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article