Local search heuristics for the multidimensional assignment problem. (English) Zbl 1194.68209
Lipshteyn, Marina (ed.) et al., Graph theory, computational intelligence and thought. Essays dedicated to Martin Charles Golumbic on the occasion of his 60th birthday. Berlin: Springer (ISBN 978-3-642-02028-5/pbk). Lecture Notes in Computer Science 5420, 100-115 (2009).
Summary: The Multidimensional Assignment Problem (MAP) (abbreviated \(s\)-AP in the case of \(s\) dimensions) is an extension of the well-known assignment problem. The most studied case of MAP is 3-AP, though the problems with larger values of \(s\) have also a number of applications. We consider several known and new MAP local search heuristics for MAP as well as their combinations. Computational experiments with three instance families are provided and discussed. As a result, we select dominating local search heuristics. One of the most interesting conclusions is that combination of two heuristics may yield a superior heuristic with respect to both solution quality and the running time.
For the entire collection see [Zbl 1178.68012].
For the entire collection see [Zbl 1178.68012].
MSC:
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
References:
| [1] | Aiex, R.M., Resende, M.G.C., Pardalos, P.M., Toraldo, G.: Grasp with path relinking for three-index assignment. INFORMS J. on Computing 17(2), 224–247 (2005) · Zbl 1239.90087 · doi:10.1287/ijoc.1030.0059 |
| [2] | Alon, N., Spencer, J.: The Probabilistic Method, 2nd edn. John Wiley, Chichester (2000) · doi:10.1002/0471722154 |
| [3] | Balas, E., Saltzman, M.J.: An algorithm for the three-index assignment problem. Oper. Res. 39(1), 150–161 (1991) · Zbl 0743.90079 · doi:10.1287/opre.39.1.150 |
| [4] | Bekker, H., Braad, E.P., Goldengorin, B.: Using bipartite and multidimensional matching to select the roots of a system of polynomial equations. In: Gervasi, O., Gavrilova, M.L., Kumar, V., Laganá, A., Lee, H.P., Mun, Y., Taniar, D., Tan, C.J.K. (eds.) ICCSA 2005. LNCS, vol. 3483, pp. 397–406. Springer, Heidelberg (2005) · doi:10.1007/11424925_43 |
| [5] | Burkard, R.E., Çela, E.: Linear assignment problems and extensions. In: Du, Z., Pardalos, P. (eds.) Handbook of Combinatorial Optimization, Dordrecht, pp. 75–149 (1999) · Zbl 1253.90131 · doi:10.1007/978-1-4757-3023-4_2 |
| [6] | Crama, Y., Spieksma, F.C.R.: Approximation algorithms for three-dimensional assignment problems with triangle inequalities. European Journal of Operational Research 60(3), 273–279 (1992) · Zbl 0761.90071 · doi:10.1016/0377-2217(92)90078-N |
| [7] | Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences. W. H. Freeman, New York (1979) · Zbl 0411.68039 |
| [8] | Grundel, D., Oliveira, C., Pardalos, P.: Asymptotic properties of random multidimensional assignment problems. Journal of Optimization Theory and Applications 122(3), 33–46 (2004) · Zbl 1082.90097 · doi:10.1023/B:JOTA.0000042592.16418.1b |
| [9] | Grundel, D.A., Pardalos, P.M.: Test problem generator for the multidimensional assignment problem. Comput. Optim. Appl. 30(2), 133–146 (2005) · Zbl 1066.90061 · doi:10.1007/s10589-005-4558-6 |
| [10] | Huang, G., Lim, A.: A hybrid genetic algorithm for the three-index assignment problem. European Journal of Operational Research 127(1), 249–257 (2006) · Zbl 1116.90070 · doi:10.1016/j.ejor.2004.09.042 |
| [11] | Knuth, D.E.: Seminumerical Algorithms, 2nd edn. The Art of Computer Programming, vol. 2. Addison-Wesley, Reading (1981) · Zbl 0477.65002 |
| [12] | Kuhn, H.W.: The hungarian method for the assignment problem. Naval Research Logistic Quarterly 2, 83–97 (1955) · Zbl 0143.41905 · doi:10.1002/nav.3800020109 |
| [13] | Microsoft. MSDN, chapter Random Class. Microsoft (2008), http://msdn2.microsoft.com/en-us/library/system.random.aspx |
| [14] | Pierskalla, W.P.: The multidimensional assignment problem. Operations Research 16, 422–431 (1968) · Zbl 0164.50003 · doi:10.1287/opre.16.2.422 |
| [15] | Robertson, A.J.: A set of greedy randomized adaptive local search procedure (grasp) implementations for the multidimensional assignment problem. Comput. Optim. Appl. 19(2), 145–164 (2001) · Zbl 1168.90594 · doi:10.1023/A:1011285402433 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
