Top

Journal of Combinatorial Optimization

Published in:

01-05-2014

Solving the Multidimensional Assignment Problem by a Cross-Entropy method

Authors: Duc Manh Nguyen, Hoai An Le Thi, Tao Pham Dinh

Published in: Journal of Combinatorial Optimization | Issue 4/2014

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

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.

previous article Faster algorithm to find anti-risk path between two nodes of an undirected graph

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Aiex RM, Resende MGC, Pardalos PM, Toraldo G (2005) GRASP with path relinking for three-index assignment. INFORMS J Comput 17(2):224–247 CrossRefMATHMathSciNet

Andrijich SM, Caccetta L (2001) Solving the multisensor data association problem. Nonlinear Anal 47:5525–5536 CrossRefMATHMathSciNet

Balas E, Saltzman MJ (1991) An algorithm for the three-index assignment problem. Oper Res 39(1):150–161 CrossRefMATHMathSciNet

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 CrossRefMATH

Burkard RE, Çela E (1997) Quadratic and three-dimensional assignment problems. In: Dell’Amico M, Maffioli F, Martello S (eds) Annotated bibliographies in combinatorial optimization. Wiley, Chichester, pp 373–392

Burkard RE, Çela E (1999) Linear assignment problems and extensions. In: Du D, Pardalos PM (eds) Handbook of combinatorial optimization. Kluwer Academic, Dordrecht, pp 75–149 (Chap 21) CrossRef

Cela E (2002) Assignment problems. In: Pardalos PM, Resende MGC (eds) Handbook of applied optimization. Oxford University Press, New York, pp 661–678 (Chap 17.9)

Clemons W, Grundel D, Jeffcoat D (2003) Applying simulated annealing on the multidimensional assignment problem. In: Proceeding of the 2nd cooperative control and optimization conference

Costa A, Dafydd O, Kroese D (2007) Convergence properties of the cross-entropy method for discrete optimization. Oper Res Lett 35(5):573–580 CrossRefMATHMathSciNet

Dambreville F (2006) Cross-entropy method: convergence issues for extended implementation. In: Proceedings of the rare event simulation conference (RESIM 2006), Bamberg, Germany

Dubin U (2002) The cross-entropy method for combinatorial optimization with applications. Master’s thesis, The Technion, Israel Institute of Technology, Haifa

Gilbert KC, Hofstra RB (1988) Multidimensional assignment problems. Decis Sci 19(2):306–321 CrossRef

Grundel D, Pardalos PM (2005) Test problem generator for the multidimensional assignment problem. Comput Optim Appl 30(2):133–146 CrossRefMATHMathSciNet

Gutin G, Karapetyan D (2009) Local search heuristics for the multidimensional assignment problem. In: Lipshteyn M, Levit VE, Mcconnell RM (eds) Graph theory, computational intelligence and thought. Lecture notes in computer science, vol 5420. Springer, Berlin, pp 100–115 CrossRef

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 CrossRefMATHMathSciNet

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

Oliveira CAS, Pardalos PM (2004) Randomized parallel algorithms for the multidimensional assignment problem. Appl Numer Math 49(1):117–133 CrossRefMATHMathSciNet

Pardalos PM, Pitsoulit LS (eds) (2000) Nonlinear assignment problems: algorithms and applications. Combinatorial optimization, vol 7. Kluwer Academic, Dordrecht

Pasiliao EL (2003) Algorithms for multidimensional assignment problems. PhD thesis, Department of Industrial and Systems Engineering, University of Florida

Pasiliao EL (2010) Local neighborhoods for the multidimensional assignment problem. In: Hirsch MJ, Pardalos PM, Murphey R (eds) Dynamics of information systems, vol 40. Springer, New York, pp 353–371 CrossRef

Pierskalla W (1968) The multidimensional assignment problem. Oper Res 16:422–431 CrossRefMATH

Poore AB (1994) Multidimensional assignment formulation of data association problems arising from multitarget and multisensor tracking. Comput Optim Appl 3:27–54 CrossRefMATHMathSciNet

Poore AB, Rijavec N (1993) A Lagrangian relaxation algorithm for multidimensional assignment problems arising from multitarget tracking. SIAM J Optim 3(3):544–563 CrossRefMATHMathSciNet

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 CrossRefMATHMathSciNet

Pusztaszeri JF, Rensing PE, Liebling TM (1996) Tracking elementary particles near their primary vertex: a combinatorial approach. J Glob Optim 9(1):41–64 CrossRefMATHMathSciNet

Rubinstein RY (1997) Optimization of computer simulation models with rare events. Eur J Oper Res 99:89–112 CrossRef

Rubinstein RY (1999) The simulated entropy method for combinatorial and continuous optimization. Methodol Comput Appl Probab 2:127–190 CrossRef

Rubinstein RY (2001) Combinatorial optimization, cross-entropy, ants and rare events. In: Uryasev S, Pardalos PM (eds) Stochastic optimization: algorithms and application. Kluwer Academic, Dordrecht, pp 304–358

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 CrossRef

Rubinstein RY, Kroese D (2004) The cross-entropy method: a unified approach to combinatorial optimization, Monté Carlo simulation, and machine learning. Springer, Berlin CrossRef

Spieksma FCR (2000) Multi index assignment problems: complexity, approximation, applications. In: Pardalos PM, Pitsoulit LS (eds) Nonlinear assignment problems: algorithms and applications. Combinatorial optimization, vol 7. Kluwer Academic, Dordrecht, pp 1–12 (Chap 1) CrossRef

Storms PPA, Spieksma FCR (2003) An LP-based algorithm for the data association problem in multitarget tracking. Comput Oper Res 30(7):1067–1085 CrossRefMATHMathSciNet

Veenman CJ, Hendriks EA, Reinders MJT (1998) A fast and robust point tracking algorithm. In: Proceedings of the fifth IEEE international conference on image processing, Chicago, pp 653–657

Title: Solving the Multidimensional Assignment Problem by a Cross-Entropy method
Authors: Duc Manh Nguyen
Hoai An Le Thi
Tao Pham Dinh
Publication date: 01-05-2014
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 4/2014
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-012-9554-z

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 4/2014

Hardness results and approximation algorithm for total liar’s domination in graphs

Algorithms with limited number of preemptions for scheduling on parallel machines

The cost of selfishness for maximizing the minimum load on uniformly related machines

Faster algorithm to find anti-risk path between two nodes of an undirected graph

Multiple L(j,1)-labeling of the triangular lattice

Paired versus double domination in K 1,r -free graphs

Premium Partner