检索结果-内蒙古大学图书馆

multidimensional assignment problem for Multipartite Entity Resolution

JOURNAL OF GLOBAL OPTIMIZATION 2022年第2期84卷 491-523页

作者： Kammerdiner, Alla Semenov, Alexander Pasiliao, Eduardo L. Univ Florida Res & Engn Educ Facil REEF Shalimar FL 32579 USA Univ Florida Herbert Wertheim Coll Engn Gainesville FL USA Munit Directorate Eglin FL USA

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.

关键词： multidimensional assignment problem Multipartite entity resolution Very large scale neighborhood search Greedy algorithm Genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

Local search heuristics for the multidimensional assignment problem

引用

JOURNAL OF HEURISTICS 2011年第3期17卷 201-249页

作者： Karapetyan, Daniel Gutin, Gregory Univ London Egham England

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.

关键词： multidimensional assignment problem Local search Neighborhood Metaheuristics

来源：评论

学校读者我要写书评

暂无评论

A New Approach to Population Sizing for Memetic Algorithms: A Case Study for the multidimensional assignment problem

引用

EVOLUTIONARY COMPUTATION 2011年第3期19卷 345-371页

作者： Karapetyan, Daniel Gutin, Gregory Royal Holloway London Univ Dept Comp Sci Egham TW20 0EX Surrey England

Memetic algorithms are known to be a powerful technique in solving hard optimization problems. To design a memetic algorithm, one needs to make a host of decisions. Selecting the population size is one of the most important among them. Most of the algorithms in the literature fix the population size to a certain constant value. This reduces the algorithm's quality since the optimal population size varies for different instances, local search procedures, and runtimes. In this paper we propose an adjustable population size. It is calculated as a function of the runtime of the whole algorithm and the average runtime of the local search for the given instance. Note that in many applications the runtime of a heuristic should be limited and, therefore, we use this bound as a parameter of the algorithm. The average runtime of the local search procedure is measured during the algorithm's run. Some coefficients which are independent of the instance and the local search are to be tuned at the design time;we provide a procedure to find these coefficients. The proposed approach was used to develop a memetic algorithm for the multidimensional assignment problem (MAP). We show that our adjustable population size makes the algorithm flexible to perform efficiently for a wide range of running times and local searches and this does not require any additional tuning of the algorithm.

关键词： Population sizing memetic algorithm evolutionary algorithm parameter tuning parameter control metaheuristic local search multidimensional assignment problem

来源：评论

学校读者我要写书评

暂无评论

Test problem generator for the multidimensional assignment problem

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2005年第2期30卷 133-146页

作者： Grundel, DA Pardalos, PM Univ Florida Dept Ind & Syst Engn Ctr Appl Optimizat Gainesville FL 32611 USA

The multidimensional assignment problem (MAPs) is a higher dimensional version of the standard linear assignment problem. Test problems of known solution are useful in exercising solution methods. A method of generating an axial MAP of controllable size with a known unique solution is presented. Certain characteristics of the generated MAPs that determine realism and difficulty are investigated.

关键词： multidimensional assignment problem test problems

来源：评论

学校读者我要写书评

暂无评论

Branch and bound algorithms for the multidimensional assignment problem

引用

OPTIMIZATION METHODS & SOFTWARE 2005年第1期20卷 127-143页

作者： Pasiliao, EL Pardalos, PM Pitsoulis, LS USAF Munit Directorate Res Lab Eglin AFB FL 32542 USA Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA Aristotle Univ Thessaloniki Dept Math Phys & Computat Sci GR-54124 Thessaloniki Greece

This work investigates two branch and bound algorithms based on different tree representations of the multidimensional assignment problem (MAP). The MAP may be depicted as either an index-based tree in which every level of the tree represents a different value of the first index or as a permutation-based tree that has vertices representing different permutation vectors of a feasible solution. We also look at the benefits of sorting the cost coefficients on each index tree level, performing a local search on either just the initial solution or every time we find a better solution, and attempting to use characteristics of previous good solutions through path relinking. The number of dimensions and the number of elements in each dimension will affect algorithm performance. We demonstrate the benefits and drawbacks of using different modifications to the branch and bound approach on different sizes of MAP instances.

关键词： multidimensional assignment problem combinatorial optimization computational results

来源：评论

学校读者我要写书评

暂无评论

A GPU Accelerated Dual-Ascent Algorithm for the multidimensional assignment problem in a Multitarget Tracking Application

引用

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 2023年第3期20卷 1706-1720页

作者： Vadrevu, Samhita Nagi, Rakesh Univ Illinois Dept Ind & Enterprise Syst Engn Urbana IL 61820 USA

We develop a Graphics Processing Unit (GPU) accelerated algorithm for the NP-Hard Multi-dimensional assignment problem (MAP), suitable for target tracking applications. First, the original MAP formulation with a quadratic objective function is reformulated using a creative linearization technique. This formulation lends itself well to Lagrangian Relaxation, which decomposes into pairwise Linear assignment problems (LAPs). These LAPs are solved in parallel and are each solved using a recent CPU-accelerated approach. Next, we propose a dual-ascent scheme for the Lagrange multiplier updates. The advantage of this scheme is that it results in monotonically increasing lower bounds and converges in a fraction of the iterations typically needed for a subgradient method. The dual-ascent technique is also parallelized for the GPU. Finally, we develop a creative gap closure scheme with M-best LAP solutions for each dimension and find the shortest path in the resulting staged graph. The algorithm is applied to the Multi-Target Tracking problem and tested on datasets for maneuverable targets. Scaling studies are also performed, and note that the processing time goes down approximately linearly in the number of CPU devices. The algorithm can efficiently solve up to a problem size of 400 targets in 400 time-frames, which corresponds to 25 billion variables, with high accuracy. Note to Practitioners-The Multi-Target Tracking problem (MTT) has been a longstanding problem with various variants and solution algorithms. Still, the problem remains challenging, especially when dealing with a large number of targets for many time frames, when solution speed and optimality are concerns. Many problems including, entity resolution, weapon target assignment, resource allocation, and data association can be formulated as MAP. Our overall algorithm, implemented with GPU acceleration enables addressing large-dimensioned MAPs, e.g., number of observed targets for a long horizon, for around 25 bi

关键词： multidimensional assignment problem multitarget tracking dual-ascent graphics processing unit (GPU) CUDA data association linear assignment problem

来源：评论

学校读者我要写书评

暂无评论

Branch and bound solution of the multidimensional assignment problem formulation of data association

引用

OPTIMIZATION METHODS & SOFTWARE 2012年第6期27卷 1101-1126页

作者： Larsen, Morten Univ Copenhagen Fac Life Sci Dept Basic Sci & Environm DK-1871 Copenhagen C Denmark

The well-known index-based tree branch and bound algorithm for solution of the multidimensional assignment problem (MAP) is extended to handle multiple assignable 0-value indices, such as found in MAPs arising from the data association problem. Three different lower bounds for partial solutions are proposed and their effectiveness examined. Computational experiments are performed on instances of different size, different feasibility structure and sparseness, and different cost structure. It is shown how the use of a small range of integer weights commonly used in computational experiments on the solution of the MAP gives misleading results. The effects of different improvements of the basic algorithm are examined, including caching of feasibility tests, sorting of branches on each level of the tree, pruning of high cost branches, promotion of branches in the best known solution, and local search. Conclusions are that all of the proposed improvements reduce running times, especially sorting and pruning.

关键词： multidimensional assignment problem data association problem branch and bound

来源：评论

学校读者我要写书评

暂无评论

Graph partitions for the multidimensional assignment problem

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2014年第1期58卷 205-224页

作者： Vogiatzis, Chrysafis Pasiliao, Eduardo L. Pardalos, Panos M. Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA Air Force Res Lab Munit Directorate Eglin AFB FL 32542 USA

In this paper, we consider two decomposition schemes for the graph theoretical description of the axial multidimensional assignment problem (MAP). The problem is defined as finding n disjoint cliques of size m with minimum total cost in K (mxn) , which is an m-partite graph with n elements per dimension. Even though the 2-dimensional assignment problem is solvable in polynomial time, extending the problem to include na parts per thousand yen3 dimensions renders it -hard. We propose two novel decomposition schemes for partitioning a MAP into disjoint subproblems, that can then be recombined to provide both upper and lower bounds to the original problem. For each of the partitioning schemes, we investigate and compare the efficiency of distinct exact and heuristic methodologies, namely augmentation and partitioning. Computational results for the methods, along with a hybrid one that consists of both partitioning schemes, are presented to depict the success of our approaches on large-scale instances.

关键词： multidimensional assignment problem Multi-sensor multi-target tracking problem Graph decomposition Parallel computing

来源：评论

学校读者我要写书评

暂无评论

Integer programming models for the multidimensional assignment problem with star costs

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2014年第3期235卷 553-568页

作者： Walteros, Jose L. Vogiatzis, Chrysafis Pasiliao, Eduardo L. Pardalos, Panos M. Univ Florida Dept Ind & Syst Engn CAO Gainesville FL 32611 USA Air Force Res Lab AFRL Munit Directorate Eglin AFB FL 32542 USA

We consider a variant of the multidimensional assignment problem (MAP) with decomposable costs in which the resulting optimal assignment is described as a set of disjoint stars. This problem arises in the context of multi-sensor multi-target tracking problems, where a set of measurements, obtained from a collection of sensors, must be associated to a set of different targets. To solve this problem we study two different formulations. First, we introduce a continuous nonlinear program and its linearization, along with additional valid inequalities that improve the lower bounds. Second, we state the standard MAP formulation as a set partitioning problem, and solve it via branch and price. These approaches were put to test by solving instances ranging from tripartite to 20-partite graphs of 4 to 30 nodes per partition. Computational results show that our approaches are a viable option to solve this problem. A comparative study is presented. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Combinatorial optimization multidimensional assignment problem Star covering Multi-sensor multi-target tracking problem Graph partitioning Branch and price

来源：评论

学校读者我要写书评

暂无评论

On optimality of a polynomial algorithm for random linear multidimensional assignment problem

引用

OPTIMIZATION LETTERS 2011年第1期5卷 153-164页

作者： Krokhmal, Pavlo A. Univ Iowa Dept Mech & Ind Engn Seamans Ctr 3131 Iowa City IA 52242 USA

We demonstrate that the linear multidimensional assignment problem with iid random costs is polynomially epsilon-approximable almost surely (a. s.) via a simple greedy heuristic, for a broad range of probability distributions of the assignment costs. Specifically, conditions on discrete and continuous distributions of the cost coefficients, including distributions with unbounded support, have been established that guarantee convergence to unity in the a. s. sense of the cost ratio between the greedy solution and optimal solution. The corresponding convergence rates have been determined.

关键词： multidimensional assignment problem Greedy heuristic Approximability Convergence almost surely

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：