Multidimensional assignment problem for multipartite entity resolution

DOI10.1007/S10898-022-01141-3MaRDI QIDQ2079699zbMATH OpenOpenAlexFDO

Authors A. R. Kammerdiner, Alexander Semenov, Eduardo L. Pasiliao

Publication date 30 September 2022

Published in Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2112.03346

zbMATH Keywords

genetic algorithmgreedy algorithmmultidimensional assignment problemmultipartite entity resolutionvery large scale neighborhood search

Mathematics Subject Classification ID

Discrete location and assignment (90B80) Combinatorial optimization (90C27)

Abstract: Multipartite entity resolution aims at integrating records from multiple datasets into one entity. We derive a mathematical formulation for a general class of record linkage problems in multipartite entity resolution across many datasets as a combinatorial optimization problem known as the multidimensional assignment problem. As a motivation for our approach, we illustrate the advantage of multipartite entity resolution over sequential bipartite matching. Because the optimization problem is NP-hard, we apply two heuristic procedures, a Greedy algorithm and very large scale neighborhood search, to solve the assignment problem and find the most likely matching of records from multiple datasets into a single entity. We evaluate and compare the performance of these algorithms and their modifications on synthetically generated data. We perform computational experiments to compare performance of recent heuristic, the very large-scale neighborhood search, with a Greedy algorithm, another heuristic for the MAP, as well as with two versions of genetic algorithm, a general metaheuristic. Importantly, we perform experiments to compare two alternative methods of re-starting the search for the former heuristic, specifically a random-sampling multi-start and a deterministic design-based multi-start. We find evidence that design-based multi-start can be more efficient as the size of databases grow large. In addition, we show that very large scale search, especially its multi-start version, outperforms simple Greedy heuristic. Hybridization of Greedy search with very large scale neighborhood search improves the performance. Using multi-start with as few as three additional runs of very large scale search offers some improvement in the performance of the very large scale search procedure. Last, we propose an approach to evaluating complexity of the very large-scale neighborhood search.

Recommendations

• Local search heuristics for the multidimensional assignment problem
• Local search heuristics for the multidimensional assignment problem
• scientific article; zbMATH DE number 1304348
• Local neighborhoods for the multidimensional assignment problem
• Entity resolution for probabilistic data

Cites work

• A three-dimensional matching model for perishable production scheduling
• An Algorithm for Solving 3-Dimensional Assignment Problems with Application to Scheduling a Teaching Practice
• Application of Monkey Search Meta-heuristic to Solving Instances of the Multidimensional Assignment Problem
• Characteristics of the Distribution of Hamming Distance Values Between Multidimensional Assignment Problem Solutions
• Data-driven combinatorial optimization for sensor-based assessment of near falls
• Finding multiple roots of a box-constrained system of nonlinear equations with a biased random-key genetic algorithm
• Graph partitions for the multidimensional assignment problem
• scientific article; zbMATH DE number 6118218 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1894377 (Why is no real title available?)
• scientific article; zbMATH DE number 3240945 (Why is no real title available?)
• Letter to the Editor—The Multidimensional Assignment Problem
• Local neighborhoods for the multidimensional assignment problem
• Local search heuristics for the multidimensional assignment problem
• On optimality of a polynomial algorithm for random linear multidimensional assignment problem
• Production planning in automated manufacturing
• Reducibility among combinatorial problems
• Solving the multidimensional assignment problem by a cross-entropy method
• The assembly of printed circuit boards: A case with multiple machines and multiple board types
• The reconstruction of latin squares with applications to school timetabling and to experimental design
• Tracking elementary particles near their primary vertex: A combinatorial approach
• Traffic assignment in communication satellites
• Very large-scale neighborhood search for the multidimensional assignment problem
• Worst case analysis of max-regret, greedy and other heuristics for multidimensional assignment and traveling salesman problems

Cited in

(1)

• Massively parallel entity matching with linear classification in low dimensional space

This page was built for publication: Multidimensional assignment problem for multipartite entity resolution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2079699)