Solving the multidimensional assignment problem by a cross-entropy method. (English) Zbl 1297.90072
Summary: The Multidimensional Assignment Problem (MAP) is a higher dimensional version of the linear assignment problem, where we find tuples of elements from given sets, such that the total cost of the tuples is minimal. The MAP has many recognized applications such as data association, target tracking, and resource planning. While the linear assignment problem is solvable in polynomial time, the MAP is NP-hard. In this work, we develop a new approach based on the Cross-Entropy (CE) methods for solving the MAP. Exploiting the special structure of the MAP, we propose an appropriate family of discrete distributions on the feasible set of the MAP that allow us to design an efficient and scalable CE algorithm. The efficiency and scalability of our method are proved via several tests on large-scale problems with up to 5 dimensions and 20 elements in each dimension, which is equivalent to a \(0-1\) linear program with 3.2 millions binary variables and 100 constraints.
Keywords:
multidimensional assignment problem (MAP); large-scale MAP; combinatorial optimization; cross-entropyReferences:
| [1] | Aiex RM, Resende MGC, Pardalos PM, Toraldo G (2005) GRASP with path relinking for three-index assignment. INFORMS J Comput 17(2):224-247 · Zbl 1239.90087 · doi:10.1287/ijoc.1030.0059 |
| [2] | Andrijich SM, Caccetta L (2001) Solving the multisensor data association problem. Nonlinear Anal 47:5525-5536 · Zbl 1042.90659 · doi:10.1016/S0362-546X(01)00656-3 |
| [3] | Balas E, Saltzman MJ (1991) An algorithm for the three-index assignment problem. Oper Res 39(1):150-161 · Zbl 0743.90079 · doi:10.1287/opre.39.1.150 |
| [4] | Bandelt HJ, Maas A, Spieksma FCR (2004) Local search heuristics for multi-index assignment problems with decomposable costs. J Oper Res Soc 55(7):694-704 · Zbl 1095.90066 · doi:10.1057/palgrave.jors.2601723 |
| [5] | Burkard, RE; Çela, E.; Dell’Amico, M. (ed.); Maffioli, F. (ed.); Martello, S. (ed.), Quadratic and three-dimensional assignment problems, 373-392 (1997), Chichester |
| [6] | Burkard, RE; Çela, E.; Du, D. (ed.); Pardalos, PM (ed.), Linear assignment problems and extensions, 75-149 (1999), Dordrecht · Zbl 1253.90131 · doi:10.1007/978-1-4757-3023-4_2 |
| [7] | Cela, E.; Pardalos, PM (ed.); Resende, MGC (ed.), Assignment problems, 661-678 (2002), New York |
| [8] | Clemons, W.; Grundel, D.; Jeffcoat, D., Applying simulated annealing on the multidimensional assignment problem (2003) |
| [9] | Costa A, Dafydd O, Kroese D (2007) Convergence properties of the cross-entropy method for discrete optimization. Oper Res Lett 35(5):573-580 · Zbl 1149.90184 · doi:10.1016/j.orl.2006.11.005 |
| [10] | Dambreville, F., Cross-entropy method: convergence issues for extended implementation, Bamberg, Germany |
| [11] | Dubin U (2002) The cross-entropy method for combinatorial optimization with applications. Master’s thesis, The Technion, Israel Institute of Technology, Haifa · Zbl 0799.90092 |
| [12] | Gilbert KC, Hofstra RB (1988) Multidimensional assignment problems. Decis Sci 19(2):306-321 · doi:10.1111/j.1540-5915.1988.tb00269.x |
| [13] | Grundel D, Pardalos PM (2005) Test problem generator for the multidimensional assignment problem. Comput Optim Appl 30(2):133-146 · Zbl 1066.90061 · doi:10.1007/s10589-005-4558-6 |
| [14] | Gutin, G.; Karapetyan, D.; Lipshteyn, M. (ed.); Levit, VE (ed.); Mcconnell, RM (ed.), Local search heuristics for the multidimensional assignment problem, No. 5420, 100-115 (2009), Berlin · Zbl 1194.68209 · doi:10.1007/978-3-642-02029-2_10 |
| [15] | Kuroki Y, Matsui T (2009) An approximation algorithm for multidimensional assignment problems minimizing the sum of squared errors. Discrete Appl Math 157(9):2124-2135 · Zbl 1170.90010 · doi:10.1016/j.dam.2007.10.013 |
| [16] | Murphey R, Pardalos PM, Pitsoulis L (1998) A greedy randomized adaptive search procedure for the multitarget multisensor tracking problem. DIMACS series, vol 40. Amer Math Soc, Providence, pp 277-302 · Zbl 0903.90178 |
| [17] | Oliveira CAS, Pardalos PM (2004) Randomized parallel algorithms for the multidimensional assignment problem. Appl Numer Math 49(1):117-133 · Zbl 1048.65063 · doi:10.1016/j.apnum.2003.11.014 |
| [18] | Pardalos PM, Pitsoulit LS (eds) (2000) Nonlinear assignment problems: algorithms and applications. Combinatorial optimization, vol 7. Kluwer Academic, Dordrecht · Zbl 0996.00025 |
| [19] | Pasiliao EL (2003) Algorithms for multidimensional assignment problems. PhD thesis, Department of Industrial and Systems Engineering, University of Florida · Zbl 1149.90184 |
| [20] | Pasiliao, EL; Hirsch, MJ (ed.); Pardalos, PM (ed.); Murphey, R. (ed.), Local neighborhoods for the multidimensional assignment problem, No. 40, 353-371 (2010), New York · Zbl 1221.90061 · doi:10.1007/978-1-4419-5689-7_19 |
| [21] | Pierskalla W (1968) The multidimensional assignment problem. Oper Res 16:422-431 · Zbl 0164.50003 · doi:10.1287/opre.16.2.422 |
| [22] | Poore AB (1994) Multidimensional assignment formulation of data association problems arising from multitarget and multisensor tracking. Comput Optim Appl 3:27-54 · Zbl 0818.93070 · doi:10.1007/BF01299390 |
| [23] | Poore AB, Rijavec N (1993) A Lagrangian relaxation algorithm for multidimensional assignment problems arising from multitarget tracking. SIAM J Optim 3(3):544-563 · Zbl 0799.90092 · doi:10.1137/0803027 |
| [24] | Poore AB, Robertson III AJ (1997) A new Lagrangian relaxation based algorithm for a class of multidimensional assignment problems. Comput Optim Appl 8(2):129-150 · Zbl 0887.90143 · doi:10.1023/A:1008669120497 |
| [25] | Pusztaszeri JF, Rensing PE, Liebling TM (1996) Tracking elementary particles near their primary vertex: a combinatorial approach. J Glob Optim 9(1):41-64 · Zbl 0860.90130 · doi:10.1007/BF00121750 |
| [26] | Rubinstein RY (1997) Optimization of computer simulation models with rare events. Eur J Oper Res 99:89-112 · Zbl 0923.90051 · doi:10.1016/S0377-2217(96)00385-2 |
| [27] | Rubinstein RY (1999) The simulated entropy method for combinatorial and continuous optimization. Methodol Comput Appl Probab 2:127-190 · Zbl 0941.65061 · doi:10.1023/A:1010091220143 |
| [28] | Rubinstein, RY; Uryasev, S. (ed.); Pardalos, PM (ed.), Combinatorial optimization, cross-entropy, ants and rare events, 304-358 (2001), Dordrecht |
| [29] | Rubinstein RY (2002) The cross-entropy method and rare-events for maximal cut and bipartition problems. ACM Trans Model Comput Simul 12(1):27-53 · Zbl 1390.90482 · doi:10.1145/511442.511444 |
| [30] | Rubinstein RY, Kroese D (2004) The cross-entropy method: a unified approach to combinatorial optimization, Monté Carlo simulation, and machine learning. Springer, Berlin · Zbl 1140.90005 · doi:10.1007/978-1-4757-4321-0 |
| [31] | Spieksma, FCR; Pardalos, PM (ed.); Pitsoulit, LS (ed.), Multi index assignment problems: complexity, approximation, applications, No. 7, 1-12 (2000), Dordrecht · Zbl 1029.90036 · doi:10.1007/978-1-4757-3155-2_1 |
| [32] | Storms PPA, Spieksma FCR (2003) An LP-based algorithm for the data association problem in multitarget tracking. Comput Oper Res 30(7):1067-1085 · Zbl 1039.90020 · doi:10.1016/S0305-0548(02)00057-6 |
| [33] | Veenman, CJ; Hendriks, EA; Reinders, MJT, A fast and robust point tracking algorithm, Chicago |
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.
