Back to Search
Start Over
SIMD tabu search for the quadratic assignment problem with graphics hardware acceleration
- Source :
- International Journal of Production Research. 48:1035-1047
- Publication Year :
- 2009
- Publisher :
- Informa UK Limited, 2009.
-
Abstract
- This paper presents a single instruction multiple data tabu search (SIMD-TS) algorithm for the quadratic assignment problem (QAP) with graphics hardware acceleration. The QAP is a classical combinatorial optimisation problem that is difficult to solve optimally for even small problems with over 30 items. By using graphic hardware acceleration, the developed SIMD-TS algorithm executes 20 to 45 times faster than traditional CPU code. The computational improvement is made possible by the utilisation of the parallel computing capability of a graphics processing unit (GPU). The speed and effectiveness of this algorithm are demonstrated on QAP library problems. The main contribution of this paper is a fast and effective SIMD-TS algorithm capable of producing results for large QAPs on a desktop personal computer equivalent to the results achieved with a CPU cluster.
- Subjects :
- Computer science
Search algorithm
Quadratic assignment problem
Strategy and Management
Graphics hardware
Graphics processing unit
Parallel algorithm
Hardware acceleration
Parallel computing
Management Science and Operations Research
Assignment problem
Industrial and Manufacturing Engineering
Tabu search
Subjects
Details
- ISSN :
- 1366588X and 00207543
- Volume :
- 48
- Database :
- OpenAIRE
- Journal :
- International Journal of Production Research
- Accession number :
- edsair.doi...........58ef032b463c4eca20d34f5be22207f8