A Parallel Approach of Simulated Annealing Using GPGPU to Solve the Quadratic Assignment Problem

被引：0

作者：

Takemoto, Lucas Arakaki ^{[1
]}

Dantas, Bianca de Almeida ^{[1
]}

Mongelli, Henrique ^{[1
]}

机构：

[1] Univ Fed Mato Grosso do Sul, Coll Comp, Campo Grande, MS, Brazil

来源：

2018 SYMPOSIUM ON HIGH PERFORMANCE COMPUTING SYSTEMS (WSCAD 2018) | 2018年

关键词：

simulated annealing; quadratic assignment problem; parallel computing; GPGPU; ALGORITHMS;

D O I：

10.1109/WSCAD.2018.00014

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In the area of combinatorial optimization, the Quadratic Assignment Problem stands out due to its complexity and its range of applications. The main goal of this work, is to analyze the performance of Simulated Annealing when applied to the QAP. In an attempt to achieve better results, besides the sequential implementations, parallel strategies using GPUs have also been adopted.

引用

页码：23 / 29

页数：7

共 22 条

[1]

[Anonymous], 1998, HDB COMBINATORIAL OP

[2] QAPLIB - A quadratic assignment problem library [J].

Burkard, RE ;

Karisch, SE ;

Rendl, F .

JOURNAL OF GLOBAL OPTIMIZATION, 1997, 10 (04) :391-403

[3] Parallelizing simulated annealing algorithms based on high-performance computer [J].

Chen, Ding-Jun ;

Lee, Chung-Yeol ;

Park, Cheol-Hoon ;

Mendes, Pedro .

JOURNAL OF GLOBAL OPTIMIZATION, 2007, 39 (02) :261-289

[4] AN IMPROVED ANNEALING SCHEME FOR THE QAP [J].

CONNOLLY, DT .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1990, 46 (01) :93-100

[5] A Parallelization of a Simulated Annealing Approach for 0-1 Multidimensional Knapsack Problem Using GPGPU [J].

Dantas, Bianca de Almeida ;

Caceres, Edson Norberto .

PROCEEDINGS OF 28TH IEEE INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING, (SBAC-PAD 2016), 2016, :134-140

[6]

Diaz J. C., 2016, COMPUTERS OPERATIONS, V36, P3002

[7] SIMULATED ANNEALING - A TOOL FOR OPERATIONAL-RESEARCH [J].

EGLESE, RW .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1990, 46 (03) :271-281

[8] An efficient implementation of parallel simulated annealing algorithm in GPUs [J].

Ferreiro, A. M. ;

Garcia, J. A. ;

Lopez-Salas, J. G. ;

Vazquez, C. .

JOURNAL OF GLOBAL OPTIMIZATION, 2013, 57 (03) :863-890

[9]

Fingler H., 2013, THESIS

[10]

Gambardella LM, 1999, J OPER RES SOC, V50, P167, DOI 10.2307/3010565

← 1 2 3 →