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

A novel framework to construct quality indicators using the linear assignment problem

TOP 2025年 1-17页

作者： Valencia-Rodriguez, Diana Cristina Coello, Carlos A. Coello CINVESTAV IPN Dept Comp Ave IPN 2508San Pedro Zacatenco Mexico City 07360 Mexico

In multi-objective optimization problems (MOPs), we aim to simultaneously find the maximum or minimum values of two or more (often conflicting) objective functions. MOPs are often found in real-world applications and, consequently, many methods have been proposed to solve them. Multi-Objective Evolutionary Algorithms (MOEAs) are popular techniques to solve MOPs due to their ease of use and their generality. Assessing the performance of MOEAs has become increasingly important due to the high number of MOEAs that have been developed in recent years. This work presents a novel framework for creating quality indicators using the linear assignment problem. In addition, we introduce two novel quality indicators generated using this framework and present examples to validate their performance. Furthermore, we present a novel algorithm called MOEA-kAP that can incorporate any indicator generated using our proposed framework as a density estimator. Our experimental results show that MOEA-kAP outperforms state-of-the-art algorithms.

关键词： Quality indicator Multi-objective optimization linear assignment problem Evolutionary algorithm

来源：评论

学校读者我要写书评

暂无评论

ORDER-STATISTICS AND THE linear assignment problem

引用

COMPUTING 1987年第2期39卷 165-174页

作者： FRENK, JBG VANHOUWENINGE, M KAN, AHGR MIT ALFRED P SLOAN SCH MANAGEMENTCAMBRIDGEMA 02139

Under mild conditions on the distribution functionF, we analyze the asymptotic behavior in expectation of the smallest order statistic, both for the case thatF is defined on (?∞, +∞) and for the case thatF is defined on (0, ∞). These results yield asymptotic estimates of the expected optiml value of the linear assignment problem under the assumption that the cost coefficients are independent random variables with distribution functionF.

关键词： 68E10 62G30 linear assignment problem order statistic asymptotic analysis

来源：评论

学校读者我要写书评

暂无评论

GPU-accelerated Hungarian algorithms for the linear assignment problem

引用

PARALLEL COMPUTING 2016年第0期57卷 52-72页

作者： Date, Ketan Nagi, Rakesh Univ Illinois Dept Ind & Enterprise Syst Engn 117 Transportat Bldg Urbana IL 61801 USA

In this paper, we describe parallel versions of two different variants (classical and alternating tree) of the Hungarian algorithm for solving the linear assignment problem (LAP). We have chosen Compute Unified Device Architecture (CUDA) enabled NVIDIA Graphics Processing Units (GPU) as the parallel programming architecture because of its ability to perform intense computations on arrays and matrices. The main contribution of this paper is an efficient parallelization of the augmenting path search phase of the Hungarian algorithm. Computational experiments on problems with up to 25 million variables reveal that the GPU-accelerated versions are extremely efficient in solving large problems, as compared to their CPU counterparts. Tremendous parallel speedups are achieved for problems with up to 400 million variables, which are solved within 13 seconds on average. We also tested multi-GPU versions of the two variants on up to 16 GPUs, which show decent scaling behavior for problems with up to 1.6 billion variables and dense cost matrix structure. (C) 2016 Elsevier B.V. All rights reserved.

关键词： linear assignment problem Parallel algorithm Graphics processing unit CUDA

来源：评论

学校读者我要写书评

暂无评论

A SEQUENTIAL DUAL SIMPLEX ALGORITHM FOR THE linear assignment problem

引用

OPERATIONS RESEARCH LETTERS 1988年第3期7卷 155-158页

作者： AKGUL, M Dept. of Industrial Engineering Bilkent University P.K. 8 06572 Maltepe Ankara Turkey

We present a sequential dual-simplex algorithm for the linear problem which has the same complexity as the algorithms of Balinski [3,4] and Goldfarb [8]: O( n 2 ) pivots, O( n 2 log n + nm ) time. Our algorithm works ... 详细信息

关键词： linear assignment problem dual-simplex strongly feasible trees polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

ON THE EXPECTED NUMBER OF assignmentS IN REDUCED MATRICES FOR THE linear assignment problem

引用

OPERATIONS RESEARCH LETTERS 1989年第6期8卷 329-335页

作者： NAWIJN, WM DORHOUT, B Faculty of Applied Mathematics University of Twente P.O. Box 217 7500 AE Enschede The Netherlands

A linear n × n assignment problem is considered for which the elements of the cost matrix are sampled from a continuous probability distribution. Based on the zero entries of the reduced matrix the expectation of the maximum number of initial assignments is determined for general n , as well as an asymptotic value for large n .

关键词： linear assignment problem matching bipartite graph occupancy problem

来源：评论

学校读者我要写书评

暂无评论

Multi-Objective Evolutionary Algorithm Based on the linear assignment problem and the Hypervolume Approximation Using Polar Coordinates (MOEA-LAPCO) 17th

Multi-Objective Evolutionary Algorithm Based on the Linear A...

引用

17th International Conference on Parallel problem Solving from Nature (PPSN)

作者： Cristina Valencia-Rodriguez, Diana Coello Coello, Carlos Artemio CINVESTAV IPN Dept Comp Sci Av IPN 2508 Mexico City 07360 DF Mexico

ISBN: (纸本)9783031147210;9783031147203

Hungarian Differential Evolution (HDE) is a Multi-Objective Evolutionary Algorithm that transforms its selection process into a linear assignment problem (LAP). In a LAP, we want to assign n agents to n tasks, where assigning an agent to a task corresponds to a cost. Thus, the aim is to minimize the overall assignment cost. It has been shown that HDE is competitive with respect to state-of-the-art algorithms. However, in this work, we identify two drawbacks in its selection process: it sometimes selects duplicated solutions and occasionally prefers weakly-dominated solutions over non-dominated ones. In this work, we propose an algorithm that tries to fix these drawbacks using the hypervolume indicator. However, since the computation of the hypervolume indicator is expensive, we adopted an approximation that uses a polar coordinates transformation. The resulting algorithm is called "Multi-Objective Evolutionary Algorithm Based on the linear assignment problem and the Hypervolume Approximation using Polar Coordinates (MOEA-LAPCO)." Our experimental results show that our proposed MOEA-LAPCO outperforms the original HDE, and it is competitive with state-of-the-art algorithms.

关键词： Multi-objective optimization linear assignment problem Hypervolume approximation

来源：评论

学校读者我要写书评

暂无评论

A Verifiable Multiparty Computation Solver for the linear assignment problem And Applications to Air Traffic Management 13

A Verifiable Multiparty Computation Solver for the Linear As...

引用

2022 Cloud Computing Security Workshop

作者： Loruenser, Thomas Wohner, Florian Krenn, Stephan AIT Austrian Inst Technol Vienna Austria

ISBN: (纸本)9781450398756

The assignment problem is an essential problem in many application fields and frequently used to optimize resource usage. The problem is well understood and various efficient algorithms exist to solve the problem. However, it was unclear what practical performance could be achieved for privacy-preserving implementations based on multiparty computation (MPC) by leveraging more efficient solution strategies than MPC-based generic simplex solvers for linear programs. We solve this question by implementing and comparing different optimized MPC algorithms to solve the assignment problem for reasonable problem sizes. Our empirical approach revealed various insights to MPC-based optimization and we measured a significant (50x) speed-up compared to the known simplex-based approach. Furthermore, we also study the overhead introduced by making the results publicly verifiable by means of non-interactive zero-knowledge proofs. By leveraging modern proof systems we also achieve significant speed-up for proof and verification times compared to the previously proposed approaches as well as compact proof sizes. Our research was motivated by a real-world use case, based on detailed discussions with representative stakeholders from the aviation industry.

关键词： linear assignment problem Privacy-Preserving Auction Multiparty Computation Verifiability

来源：评论

学校读者我要写书评

暂无评论

A population-based algorithm for solving linear assignment problems with two objectives

引用

COMPUTERS & OPERATIONS RESEARCH 2017年第Mar.期79卷 291-303页

作者： Gandibleux, Xavier Morita, Hiroyuki Katoh, Naoki Univ Nantes CNRS UMR 6597 Fac Sci & TechnolIRCCyN 2 Rue HoussiniereBP 92208 F-44322 Nantes 03 France Osaka Prefecture Univ Coll Sustainable Syst Sci Sakai Osaka 5998231 Japan Kyoto Univ Grad Sch Engn Kyoto 6068501 Japan

The paper presents a population-based algorithm for computing approximations of the efficient solution set for the linear assignment problem with two objectives. This is a multiobjective metaheuristic based on the intensive use of three operators a local search, a crossover and a path-relinking performed on a population composed only of elite solutions. The initial population is a set of feasible solutions, where each solution is one optimal assignment for an appropriate weighted sum of two objectives. Genetic information is derived from the elite solutions, providing a useful genetic heritage to be exploited by crossover operators. An upper bound set, defined in the objective space, provides one acceptable limit for performing a local search. Results reported using referenced data sets have shown that the heuristic is able to quickly find a very good approximation of the efficient frontier, even in situation of heterogeneity of objective functions. In addition, this heuristic has two main advantages. It is based on simple easy-to-implement principles, and it does not need a parameter tuning phase. (C) 2017 Published by Elsevier Ltd.

关键词： Multiobjective optimization linear assignment problem Metaheuristic Heterogeneous functions

来源：评论

学校读者我要写书评

暂无评论

Two classes of Quadratic assignment problems that are solvable as linear assignment problems

引用

DISCRETE OPTIMIZATION 2011年第3期8卷 446-451页

作者： Erdogan, Gunes Tansel, Barbaros C. Ozyegin Univ Dept Ind Engn TR-34662 Istanbul Turkey Bilkent Univ Dept Ind Engn TR-06800 Ankara Turkey

The Quadratic assignment problem is one of the hardest combinatorial optimization problems known. We present two new classes of instances of the Quadratic assignment problem that can be reduced to the linear assignment problem and give polynomial time procedures to check whether or not an instance is an element of these classes. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Quadratic assignment problem linear assignment problem Computational complexity Polynomial time solvability

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：