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

Level 2 Reformulation linearization Technique-Based Parallel Algorithms for Solving Large Quadratic assignment problems on Graphics Processing Unit Clusters

引用

INFORMS JOURNAL ON COMPUTING 2019年第4期31卷 771-789页

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

This paper discusses efficient parallel algorithms for obtaining strong lower bounds and exact solutions for large instances of the quadratic assignment problem (QAP). Our parallel architecture is comprised of both multicore processors and compute unified device architecture-enabled NVIDIA graphics processing units (GPUs) on the Blue Waters Supercomputing Facility at the University of Illinois at Urbana-Champaign. We propose novel parallelization of the Lagrangian dual ascent algorithm on the GPUs, which is used for solving a QAP formulation based on the level-2 reformulation linearization technique. The linear assignment subproblems in this procedure are solved using our accelerated Hungarian algorithm [Date K, Rakesh N (2016) GPU-accelerated Hungarian algorithms for the linear assignment problem. Parallel Computing 57:52-72.]. We embed this accelerated dual-ascent algorithm in a parallel branch-and-bound scheme and conduct extensive computational experiments on single and multiple GPUs, using problem instances with up to 42 facilities from the quadratic assignment problem library (QAPLIB). The experiments suggest that our GPU-based approach is scalable, and it can be used to obtain tight lower bounds on large QAP instances. Our accelerated branch-and-bound scheme is able to comfortably solve Nugent and Taillard instances (up to 30 facilities) from the QAPLIB, using a modest number of GPUs.

关键词： quadratic assignment problem linear assignment problem branch-and-bound parallel algorithm graphics processing unit CUDA RLT2

来源：评论

学校读者我要写书评

暂无评论

A ranked linear assignment approach to Bayesian classification

引用

APPLIED MATHEMATICS AND COMPUTATION 2005年第1期162卷 265-281页

作者： Danchick, R 10336 Wilshire Blvd 101 Los Angeles CA 90024 USA

We show how a ranked linear assignment algorithm can be used to solve the problem of accurately matching the n components of a random data sample vector to n data classes. It is assumed that each component of the random data sample vector corresponds to exactly one data class and, conversely, that each data class corresponds to exactly one data sample vector component, and that the sample data vector components are always arranged in the same but unknown order. That is, we assume that the mth sample random vector, X-m = [x(1)(m),x(2)(m),x(3)(m),...,x(n)(m)](T), of sample-to-sample independent normally distributed random vector components has the property: x(i)(m) is an element of N(mu(phi(i)),sigma(phi(i))(2)), mu(i) not equal mu(j) if i not equal j, i,j = 1,2...,n for some fixed but unknown permutation phi in the symmetric group S-n on the letters [1,2,3,...n], m = 1, 2, 3,..., M,... We derive the averaged permutation matrix representation over S-n, given the mean of M data vector samples. This matrix turns out to be a doubly stochastic matrix, P-M, whose (i,j) element is the probability that data stream component i corresponds to class j, given the sample mean vector (K) over bar (M). We prove that P-M converges to phi in probability. Moreover, it is shown that P-M can be accurately approximated by extending from the solution of the classical linear assignment problem of finding the permutation with maximum likelihood to the solution of the ranked linear assignment problem in which a small number of permutations with rapidly decreasing likelihoods are identified. (C) 2004 Elsevier Inc. All rights reserved.

关键词： Bayesian classification linear assignment problem ranked assignments probability

来源：评论

学校读者我要写书评

暂无评论

An assignment-Based Approach to Efficient Real-Time City-Scale Taxi Dispatching

引用

IEEE INTELLIGENT SYSTEMS 2016年第1期31卷 68-77页

作者： Maciejewski, Michal Bischoff, Joschka Nagel, Kai Poznan Univ Tech Div Transport Syst Poznan Poland Tech Univ Berlin Dept Transport Syst Planning & Transport Telemat Berlin Germany

This study proposes and evaluates an efficient real-time taxi dispatching strategy that solves the linear assignment problem to find a globally optimal taxi-to-request assignment at each decision epoch. The authors compare the assignment-based strategy with two popular rule-based strategies. They evaluate dispatching strategies in detail in the city of Berlin and the neighboring region of Brandenburg using the microscopic large-scale MATSim simulator. The assignment-based strategy produced better results for both drivers (less idle driving) and passengers (less waiting). However, computing the assignments for thousands of taxis in a huge road network turned out to be computationally demanding. Certain adaptations pertaining to the cost matrix calculation were necessary to increase the computational efficiency and assure real-time responsiveness.

关键词： automobiles intelligent transportation systems knowledge based systems road traffic transportation assignment-based strategy computational efficiency cost matrix calculation decision epoch drivers huge road network less idle driving less waiting linear assignment problem microscopic large-scale MATSim simulator optimal taxi-to-request assignment passengers real-time city-scale taxi dispatching strategy real-time responsiveness rule-based strategies Computational modeling Dispatching Heuristic algorithms Public transportation Real-time systems Vehicle dynamics Vehicles MATSim Online taxi dispatching assignment problem dynamic vehicle routing floating car data intelligent systems microscopic traffic simulation

来源：评论

学校读者我要写书评

暂无评论

An algorithm for ranking assignments using reoptimization

引用

COMPUTERS & OPERATIONS RESEARCH 2008年第11期35卷 3714-3726页

作者： Pedersen, Christian Roed Nielsen, Lars Relund Andersen, Kim Allan Univ Aarhus Aarhus Sch Business Dept Business Studies DK-8210 Aarhus V Denmark Univ Aarhus Dept Operat Res DK-8000 Aarhus C Denmark Univ Aarhus Dept Genet & Biotechnol Res Unit Stat & Decis Anal DK-8830 Tjele Denmark

We consider the problem of ranking assignments according to cost in the classical linear assignment problem. An algorithm partitioning the set of possible assignments, as suggested by Murty, is presented where, for each partition, the optimal assignment is calculated using a new reoptimization technique. Its computational performance is compared with all available implementations of algorithms with the same time complexity. The results are encouraging. (c) 2007 Elsevier Ltd. All rights reserved.

关键词： linear assignment problem ranking K best solutions

来源：评论

学校读者我要写书评

暂无评论

linearizable special cases of the QAP

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2016年第3期31卷 1269-1279页

作者： Cela, Eranda Deineko, Vladimir G. Woeginger, Gerhard J. Graz Univ Technol Inst Optimierung & Diskrete Math Steyrergasse 30 A-8010 Graz Austria Univ Warwick Warwick Business Sch Coventry CV4 7AL W Midlands England Tech Univ Eindhoven Dept Math & Comp Sci POB 513 NL-5600 MB Eindhoven Netherlands

We consider special cases of the quadratic assignment problem (QAP) that are linearizable in the sense of Bookhold. We provide combinatorial characterizations of the linearizable instances of the weighted feedback arc set QAP, and of the linearizable instances of the traveling salesman QAP. As a by-product, this yields a new well-solvable special case of the weighted feedback arc set problem.

关键词： Combinatorial optimization Quadratic assignment problem linear assignment problem Computational complexity

来源：评论

学校读者我要写书评

暂无评论

Algorithms and codes for dense assignment problems: the state of the art

引用

DISCRETE APPLIED MATHEMATICS 2000年第1-2期100卷 17-48页

作者： Dell'Amico, M Toth, P Univ Modena DISMI I-42100 Reggio Emilia Italy Univ Bologna DEIS I-40136 Bologna Italy

The paper considers the classic linear assignment problem with a min-sum objective function, and the most efficient and easily available codes for its solution, We first give a survey describing the different approaches in the literature, presenting their implementations, and pointing out similarities and differences, Then we select eight codes and we introduce a wide set of dense instances containing both randomly generated and benchmark problems. Finally we discuss the results of extensive computational experiments obtained by solving the above instances with the eight codes, both on a workstation with Unix operating system and on a personal computer running under Windows 95. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： linear assignment problem experimental evaluation comparison of algorithms dense matrices

来源：评论

学校读者我要写书评

暂无评论

On the needs for MaaS platforms to handle competition in ridesharing mobility

引用

TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES 2019年 108卷 269-288页

作者： Pandey, Venktesh Monteil, Julien Gambella, Claudio Simonetto, Andrea Univ Texas Austin Austin TX 78712 USA IBM Res Ireland Dublin Ireland

Ridesharing has been emerging as a new type of mobility. However, the early promises of ridesharing for alleviating congestion in cities may be undermined by a number of challenges, including the growing number of proposed services and the subsequent increasing number of vehicles, as a natural consequence of competition. In this work, we present optimization-based approaches to model cooperation and competition between multiple ridesharing companies, in a real-time on-demand setting. A recent trend relies on solving the integrated combination of Dial-A-Ride problems (DARP), which compute the cost of assigning incoming requests to vehicle routes, plus linear assignment problems (LAP), which assign vehicles to requests. While the DARPs, are solved at the level of the vehicles of each company, we introduce cooperative and competitive approaches to solve the LAP. The cooperative model, which could make use of Mobility as a Service platforms, is shown to solve the LAP to optimality following closely results from the literature, and limiting the amount of information the companies are required to share. We investigate how a realistic model of competition deviates from this optimality and provide worst case bounds. We evaluate these models with respect to a centralized model on one-week instances of the New York City taxi dataset. Model variants coping with noise in the travel time estimations, bias in the assignment costs, and preferences in the competitive case are also presented and validated. The computational results suggest that cooperation among ridesharing companies can be conducted in such a way to limit the degradation of the level of service with respect to a centralized model. Finally, we argue that the competition can lower the quality of the ridesharing service, especially in the case customer preferences are accommodated.

关键词： Dynamic ridesharing On-demand mobility linear assignment problem Competition

来源：评论

学校读者我要写书评

暂无评论

Fast block distributed CUDA implementation of the Hungarian algorithm

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2019年 130卷 50-62页

作者： Lopes, Paulo A. C. Yadav, Satyendra Singh Ilic, Aleksandar Patra, Sarat Kumar Univ Lisbon Inst Engn Sistemas & Comp Invest & Desenvolviment Inst Super Tecn INESC ID IST UL Rua Alves Redol 9 P-1000029 Lisbon Portugal Natl Inst Technol Rourkela Dept Elect & Commun Engn Rourkela Odisha India Indian Inst Informat Technol Dept Comp Sci Engn Vadodara India

The Hungarian algorithm solves the linear assignment problem in polynomial time. A GPU/CUDA implementation of this algorithm is proposed. GPUs are massive parallel machines. In this implementation, the alternating path search phase of the algorithm is distributed by several blocks in a way to minimize global device synchronization. This phase is very important and has a big contribution to the execution time. Other advanced features also implemented are: parallel graph traversal;the parallel detection of multiple alternating paths in a single iteration;a simplified and fast matrix compression that stores the zeros of the slack matrix, resulting in very fast graph traversal;highly optimized reductions for the initial slack matrix calculation and update. This results in a fast implementation for moderate size problems. (C) 2019 Elsevier Inc. All rights reserved.

关键词： Hungarian algorithm linear assignment problem GPU

来源：评论

学校读者我要写书评

暂无评论

Power allocation and subchannel pairing for BER minimization in MIMO-OFDM AF relay systems

引用

ANNALS OF TELECOMMUNICATIONS 2020年第5-6期75卷 175-184页

作者： Shamsesalehi, Mohammad Attarizi, Yasser Rajabi, Roozbeh Qom Univ Technol Elect & Comp Engn Qom 151937195 Iran

The present study investigates the problem of bit error rate minimization in multi-input-multi-output orthogonal frequency-division multiplexing amplify-and-forward relay systems. It is supposed that channels are frequency selective fading and under a total power constraint. In the multi-antenna transmitter, an independent symbol sequence is transmitted from each antenna. Zero forcing beamforming is performed in the reception and transmission of the relay to cancel out the inter-antenna interference. A power allocation and subchannel pairing scheme is considered as the optimization method. The goal of the optimization problem is to achieve the best bit error rate performance by applying a joint power allocation and subchannel pairing approach for all antennas. To deal with subchannel pairing, at first, we formulate it as a linear assignment problem and then Jonker-Volgenant algorithm is used to solve this problem. The joint scheme is compared with separate power allocation and subchannel pairing for each antenna as the main target. It is found that the joint scheme is superior to the separate method. Simulation results show that the proposed inter-antenna power allocation and subchannel pairing scheme can improve bit error rate and mean square error dramatically compared with separate subchannel pairing and power allocation at the cost of a little increase in complexity.

关键词： MIMO-OFDM AF relay Subchannel pairing Power allocation linear assignment problem

来源：评论

学校读者我要写书评

暂无评论

Real-time multitarget tracking for sensor-based sorting A new implementation of the auction algorithm for graphics processing units

引用

JOURNAL OF REAL-TIME IMAGE PROCESSING 2019年第6期16卷 2261-2272页

作者： Maier, Georg Pfaff, Florian Wagner, Matthias Pieper, Christoph Gruna, Robin Noack, Benjamin Kruggel-Emden, Harald Laengle, Thomas Hanebeck, Uwe D. Wirtz, Siegmar Scherer, Viktor Beyerer, Juergen Fraunhofer Inst Optron Syst Technol & Image Exploitat IOSB Fraunhoferstr 1 D-76131 Karlsruhe Germany Karlsruhe Inst Technol Intelligent Sensor Actuator Syst Lab ISAS Karlsruhe Germany Ruhr Univ Bochum Dept Energy Plant Technol LEAT Bochum Germany TU Berlin Mech Proc Engn & Solids Proc Berlin Germany

Utilizing parallel algorithms is an established way of increasing performance in systems that are bound to real-time restrictions. Sensor-based sorting is a machine vision application for which firm real-time requirements need to be respected in order to reliably remove potentially harmful entities from a material feed. Recently, employing a predictive tracking approach using multitarget tracking in order to decrease the error in the physical separation in optical sorting has been proposed. For implementations that use hard associations between measurements and tracks, a linear assignment problem has to be solved for each frame recorded by a camera. The auction algorithm can be utilized for this purpose, which also has the advantage of being well suited for parallel architectures. In this paper, an improved implementation of this algorithm for a graphics processing unit (GPU) is presented. The resulting algorithm is implemented in both an OpenCL and a CUDA based environment. By using an optimized data structure, the presented algorithm outperforms recently proposed implementations in terms of speed while retaining the quality of output of the algorithm. Furthermore, memory requirements are significantly decreased, which is important for embedded systems. Experimental results are provided for two different GPUs and six datasets. It is shown that the proposed approach is of particular interest for applications dealing with comparatively large problem sizes.

关键词： linear assignment problem Sensor-based sorting Parallel algorithm Graphics processing unit

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：