Local search heuristics for the multidimensional assignment problem. (English) Zbl 1214.90078
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\) also have a large number of applications. We consider several known neighborhoods, generalize them and propose some new ones. The heuristics are evaluated both theoretically and experimentally and dominating algorithms are selected. We also demonstrate that a combination of two neighborhoods may yield a heuristics which is superior to both of its components.
MSC:
| 90B80 | Discrete location and assignment |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Aiex, R.M., Resende, M.G.C., Pardalos, P.M., Toraldo, G.: Grasp with path relinking for three-index assignment. INFORMS J. Comput. 17(2), 224–247 (2005) · Zbl 1239.90087 · doi:10.1287/ijoc.1030.0059 |
| [2] | Alon, N., Spencer, J.: The Probabilistic Method, 2nd edn. Wiley, New York (2000) |
| [3] | Andrijich, S.M., Caccetta, L.: Solving the multisensor data association problem. Nonlinear Anal. 47(8), 5525–5536 (2001) · Zbl 1042.90659 · doi:10.1016/S0362-546X(01)00656-3 |
| [4] | 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 |
| [5] | Bandelt, H.J., Maas, A., Spieksma, F.C.R.: Local search heuristics for multi-index assignment problems with decomposable costs. J. Oper. Res. Soc. 55(7), 694–704 (2004) · Zbl 1095.90066 · doi:10.1057/palgrave.jors.2601723 |
| [6] | Bekker, H., Braad, E.P., Goldengorin, B.: Using bipartite and multidimensional matching to select the roots of a system of polynomial equations. In: Computational Science and Its Applications–ICCSA 2005. Lecture Notes Comp. Sci., vol. 3483, pp. 397–406. Springer, Berlin (2005) · Zbl 1121.90402 |
| [7] | Burkard, R.E., Çela, E.: Linear assignment problems and extensions. In: Du, Z., Pardalos, P. (eds.) Handbook of Combinatorial Optimization, pp. 75–149. Kluwer Academic, Dordrecht (1999) · Zbl 1253.90131 |
| [8] | Burkard, R.E., Klinz, B., Rudolf, R.: Perspectives of Monge properties in optimization. Discrete Appl. Math. 70(2), 95–161 (1996a) · Zbl 0856.90091 · doi:10.1016/0166-218X(95)00103-X |
| [9] | Burkard, R.E., Rudolf, R., Woeginger, G.J.: Three-dimensional axial assignment problems with decomposable cost coefficients. Technical Report 238, Graz (1996b) · Zbl 0846.90090 |
| [10] | Clemons, W.K., Grundel, D.A., Jeffcoat, D.E.: In: Theory and Algorithms for Cooperative Systems. Applying Simulated Annealing to the Multidimensional Assignment Problem, pp. 45–61. World Scientific, Singapore (2004) · Zbl 1114.90453 |
| [11] | Crama, Y., Spieksma, F.C.R.: Approximation algorithms for three-dimensional assignment problems with triangle inequalities. Eur. J. Oper. Res. 60(3), 273–279 (1992) · Zbl 0761.90071 · doi:10.1016/0377-2217(92)90078-N |
| [12] | Frieze, A.M., Yadegar, J.: An algorithm for solving 3-dimensional assignment problems with application to scheduling a teaching practice. J. Oper. Res. Soc. 32, 989–995 (1981) · Zbl 0464.90055 |
| [13] | Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences. Freeman, New York (1979) · Zbl 0411.68039 |
| [14] | 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 |
| [15] | Grundel, D., Oliveira, C., Pardalos, P.: Asymptotic properties of random multidimensional assignment problems. J. Optim. Theory Appl. 122(3), 33–46 (2004) · Zbl 1082.90097 |
| [16] | Gutin, G., Karapetyan, D.: Greedy like algorithms for the traveling salesman problem and multidimensional assignment problem. In: Advances in Greedy Algorithms. I-Tech (2008) |
| [17] | Gutin, G., Karapetyan, D.: A selection of useful theoretical tools for the design and analysis of optimization heuristics. Memetic Comput. 1(1), 25–34 (2009) · doi:10.1007/s12293-008-0001-8 |
| [18] | Gutin, G., Goldengorin, B., Huang, J.: Worst case analysis of max-regret, greedy and other heuristics for multidimensional assignment and traveling salesman problems. J. Heuristics 14(2), 169–181 (2008) · Zbl 1173.90512 · doi:10.1007/s10732-007-9033-3 |
| [19] | Harris, J.M., Hirst, J.L., Mossinghoff, M.J.: Combinatorics and Graph Theory. Mathematics (2008) · Zbl 1170.05001 |
| [20] | Huang, G., Lim, A.: A hybrid genetic algorithm for the three-index assignment problem. Eur. J. Oper. Res. 172(1), 249–257 (2006) · Zbl 1116.90070 · doi:10.1016/j.ejor.2004.09.042 |
| [21] | Isler, V., Khanna, S., Spletzer, J., Taylor, C.J.: Target tracking with distributed sensors: The focus of attention problem. Comput. Vis. Image Underst. J. 100(1–2), 225–247 (2005). Special Issue on Attention and Performance in Computer Vision · doi:10.1016/j.cviu.2004.10.008 |
| [22] | Karapetyan, D.: http://www.cs.rhul.ac.uk/Research/ToC/publications/Karapetyan/ (2009) |
| [23] | Karapetyan, D., Gutin, G., Goldengorin, B.: Empirical evaluation of construction heuristics for the multidimensional assignment problem. In: Chan, J., Daykin, J.W., Rahman, M.S. (eds.) London Algorithmics 2008: Theory and Practice. Texts in Algorithmics, pp. 107–122. College Sci. Publ., State College (2009) · Zbl 1219.90088 |
| [24] | Krokhmal, P., Grundel, D., Pardalos, P.: Asymptotic behavior of the expected optimal value of the multidimensional assignment problem. Math. Program. 109(2–3), 525–551 (2007) · Zbl 1147.90033 · doi:10.1007/s10107-006-0036-x |
| [25] | Kuhn, H.W.: The hungarian method for the assignment problem. Nav. Res. Logist. Q. 2, 83–97 (1955) · Zbl 0143.41905 · doi:10.1002/nav.3800020109 |
| [26] | Kuroki, Y., Matsui, T.: An approximation algorithm for multidimensional assignment problems minimizing the sum of squared errors. Discrete Appl. Math. 157(9), 2124–2135 (2007) · Zbl 1170.90010 · doi:10.1016/j.dam.2007.10.013 |
| [27] | Murphey, R., Pardalos, P., Pitsoulis, L.: A GRASP for the multitarget multisensor tracking problem. Networks Discrete Math. Theor. Comput. Sci. Ser. 40, 277–302 (1998) · Zbl 0903.90178 |
| [28] | Oliveira, C.A.S., Pardalos, P.M.: Randomized parallel algorithms for the multidimensional assignment problem. Appl. Numer. Math. 49, 117–133 (2004) · Zbl 1048.65063 · doi:10.1016/j.apnum.2003.11.014 |
| [29] | Pardalos, P.M., Pitsoulis, L.S.: Nonlinear Assignment Problems. Springer, Berlin (2000) |
| [30] | Pardalos, P.M., Pitsoulis, L.S.: In: Quadratic and Multidimensional Assignment Problems. Nonlinear Optimization and Applications, vol. 2, pp. 235–276. Kluwer Academic, Dordrecht (2000) · Zbl 0962.90040 |
| [31] | Pasiliao, E.L., Pardalos, P.M., Pitsoulis, L.S.: Branch and bound algorithms for the multidimensional assignment problem. Optim. Methods Softw. 20(1), 127–143 (2005) · Zbl 1087.90041 · doi:10.1080/10556780410001697695 |
| [32] | Pierskalla, W.P.: The multidimensional assignment problem. Oper. Res. 16, 422–431 (1968) · Zbl 0164.50003 · doi:10.1287/opre.16.2.422 |
| [33] | Pusztaszeri, J., Rensing, P., Liebling, Th.M.: Tracking elementary particles near their primary vertex: a combinatorial approach. J. Glob. Optim. 9, 41–64 (1996) · Zbl 0860.90130 · doi:10.1007/BF00121750 |
| [34] | Rardin, R.L., Uzsoy, R.: Experimental evaluation of heuristic optimization algorithms: A tutorial. J. Heuristics 7(3), 261–304 (2001) · Zbl 0972.68634 · doi:10.1023/A:1011319115230 |
| [35] | 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 |
| [36] | Spieksma, F.C.R.: In: Multi Index Assignment Problems: Complexity, Approximation, Applications. Nonlinear Assignment Problems, Algorithms and Application, pp. 1–12. Kluwer Academic, Norwell (2000) · Zbl 1029.90036 |
| [37] | Spieksma, F., Woeginger, G.: Geometric three-dimensional assignment problems. Eur. J. Oper. Res. 91, 611–618 (1996) · Zbl 0918.90124 · doi:10.1016/0377-2217(95)00003-8 |
| [38] | Talbi, E.-G.: Metaheuristics: From Design to Implementation. Wiley, New York (2009) · Zbl 1190.90293 |
| [39] | Veenman, C.J., Reinders, M.J.T., Backer, E.: Establishing motion correspondence using extended temporal scope. Artif. Intell. 145(1–2), 227–243 (2003) · Zbl 1082.68840 · doi:10.1016/S0004-3702(02)00380-6 |
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.
