Solving the Multidimensional Assignment Problem by a Cross-Entropy method

Duc Manh Nguyen (), Hoai An Le Thi () and Tao Pham Dinh ()
Additional contact information
Duc Manh Nguyen: National Institute for Applied Sciences (INSA) – Rouen
Hoai An Le Thi: University of Lorraine
Tao Pham Dinh: National Institute for Applied Sciences (INSA) – Rouen

Journal of Combinatorial Optimization, 2014, vol. 27, issue 4, No 12, 808-823

Abstract: 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.

Keywords: Multidimensional Assignment Problem (MAP); Large-scale MAP; Combinatorial optimization; Cross-Entropy (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-012-9554-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:27:y:2014:i:4:d:10.1007_s10878-012-9554-z

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-012-9554-z

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().