A GPU implementation of the Simulated Annealing Heuristic for the Quadratic Assignment Problem

2012/08/13 by Gerald Paul, Paul, Gerald
Engineering · #Distributed #FOS: Computer and information sciences #Optimization and Packing Problems #Parallel #Scheduling and Optimization Algorithms #Vehicle Routing Optimization Methods #and Cluster Computing (cs.DC)

paper · pdf · doi:10.48550/arxiv.1208.2675

openalex publication_date 2012/08/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The quadratic assignment problem (QAP) is one of the most difficult combinatorial optimization problems. An effective heuristic for obtaining approximate solutions to the QAP is simulated annealing (SA). Here we describe an SA implementation for the QAP which runs on a graphics processing unit (GPU). GPUs are composed of low cost commodity graphics chips which in combination provide a powerful platform for general purpose parallel computing. For SA runs with large numbers of iterations, we find performance 50-100 times better than that of a recent non-parallel but very efficient implementation of SA for the QAP

Related

• An efficient implementation of the simulated annealing heuristic for the quadratic assignment problem
• GPU-accelerated Parallel Solutions to the Quadratic Assignment Problem
• RLT2-based Parallel Algorithms for Solving Large Quadratic Assignment Problems on Graphics Processing Unit Clusters
• Solving the Quadratic Assignment Problem on heterogeneous environment (CPUs and GPUs) with the application of Level 2 Reformulation and Linearization Technique
• Digital Annealer for quadratic unconstrained binary optimization: a comparative performance analysis