Abstract
Due to physical limits, hardware development no longer results in higher speed for sequential algorithms,
but rather in increased parallelism. Modern commodity PCs include a multi-core CPU and at least one
GPU, providing a low cost, easily accessible heterogeneous environment for high performance computing.
New solution methods that combine task parallelization and stream processing and self-adapt to the
hardware at hand are needed to fully exploit modern computer architectures and profit from future
hardware developments.
In this talk, we first give an introduction to modern PC architectures and the GPU [1], and survey the
literature on GPU-based solution methods in discrete optimization [2] that currently consists of some 100
papers. Many of them describe GPU implementations of well-known metaheuristics and report impressive
speedups relative to a sequential version [3]. As for applications and problems studied, 26 papers describe
research on routing problems of which 9 focus on the Shortest Path Problem, 15 discuss the Travelling
Salesman Problem, and only 2 study the Vehicle Routing Problem.
In the second part of this talk we present a GPU-based TSP solver which is inspired by the highly successful
and leading TSP solver LKH2 of Keld Helsgaun [4,5]. To our knowledge this is the first GPU based TSPsolver
that provides a competitive solution quality for large sized TSP problems. During the development of
the GPU solver we examined two different ways of adapting the Lin-Kernighan heuristic to the dataparallelism
of the GPU. In contrast to LKH2, one of these approaches leads to fewer random restarts, but
with more heavy and involved local searches. The other version uses the same number of restarts as in
LKH2, but with a different distribution into the two kinds of restarts in LKH2. For a selected number of
large-scale instances we will present numerical results.
References
[1] Brodtkorb A.R., Hagen T.R., Schulz C., Hasle, G.: GPU Computing in Discrete Optimization - Part I:
Introduction to the GPU. EURO J Transp Logist (2013) 2:129–157.
[2] Schulz C., Hasle G., Brodtkorb A.R., Hagen T.R.: GPU Computing in Discrete Optimization - Part II:
Survey Focused on Routing Problems. EURO J Transp Logist (2013) 2:159–186.
[3] Talbi E.-G., Hasle G.: Metaheuristics on the GPU. Editorial. Special Issue Journal of Parallel and
Distributed Computing, Volume 73, Issue 1, January 2013, Pages 1-3, ISSN 0743-7315,
10.1016/j.jpdc.2012.09.014.
[4] Helsgaun, K.: An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic.
DATALOGISKE SKRIFTER (Writings on Computer Science), No. 81, 1998, Roskilde University.
[5] Helsgaun, K.: An Effective Implementation of K-opt Moves for the Lin-Kernighan TSP Heuristic.
DATALOGISKE SKRIFTER (Writings on Computer Science), No. 109, 2006, Roskilde University
(Revised November 2007).
but rather in increased parallelism. Modern commodity PCs include a multi-core CPU and at least one
GPU, providing a low cost, easily accessible heterogeneous environment for high performance computing.
New solution methods that combine task parallelization and stream processing and self-adapt to the
hardware at hand are needed to fully exploit modern computer architectures and profit from future
hardware developments.
In this talk, we first give an introduction to modern PC architectures and the GPU [1], and survey the
literature on GPU-based solution methods in discrete optimization [2] that currently consists of some 100
papers. Many of them describe GPU implementations of well-known metaheuristics and report impressive
speedups relative to a sequential version [3]. As for applications and problems studied, 26 papers describe
research on routing problems of which 9 focus on the Shortest Path Problem, 15 discuss the Travelling
Salesman Problem, and only 2 study the Vehicle Routing Problem.
In the second part of this talk we present a GPU-based TSP solver which is inspired by the highly successful
and leading TSP solver LKH2 of Keld Helsgaun [4,5]. To our knowledge this is the first GPU based TSPsolver
that provides a competitive solution quality for large sized TSP problems. During the development of
the GPU solver we examined two different ways of adapting the Lin-Kernighan heuristic to the dataparallelism
of the GPU. In contrast to LKH2, one of these approaches leads to fewer random restarts, but
with more heavy and involved local searches. The other version uses the same number of restarts as in
LKH2, but with a different distribution into the two kinds of restarts in LKH2. For a selected number of
large-scale instances we will present numerical results.
References
[1] Brodtkorb A.R., Hagen T.R., Schulz C., Hasle, G.: GPU Computing in Discrete Optimization - Part I:
Introduction to the GPU. EURO J Transp Logist (2013) 2:129–157.
[2] Schulz C., Hasle G., Brodtkorb A.R., Hagen T.R.: GPU Computing in Discrete Optimization - Part II:
Survey Focused on Routing Problems. EURO J Transp Logist (2013) 2:159–186.
[3] Talbi E.-G., Hasle G.: Metaheuristics on the GPU. Editorial. Special Issue Journal of Parallel and
Distributed Computing, Volume 73, Issue 1, January 2013, Pages 1-3, ISSN 0743-7315,
10.1016/j.jpdc.2012.09.014.
[4] Helsgaun, K.: An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic.
DATALOGISKE SKRIFTER (Writings on Computer Science), No. 81, 1998, Roskilde University.
[5] Helsgaun, K.: An Effective Implementation of K-opt Moves for the Lin-Kernighan TSP Heuristic.
DATALOGISKE SKRIFTER (Writings on Computer Science), No. 109, 2006, Roskilde University
(Revised November 2007).