Massively parallel tabu search for the quadratic assignment problem |
| |
Authors: | Jaishankar Chakrapani Jadranka Skorin-Kapov |
| |
Affiliation: | (1) Department of Applied Mathematics and Statistics, State University of New York at Stony Brook, 11794 Stony Brook, NY, USA;(2) Harriman School for Management and Policy, State University of New York at Stony Brook, 11794 Stony Brook, NY, USA |
| |
Abstract: | A new heuristic algorithm to perform tabu search on the Quadratic Assignment Problem (QAP) is developed. A massively parallel implementation of the algorithm on the Connection Machine CM-2 is provided. The implementation usesn2 processors, wheren is the size of the problem. The elements of the algorithm, calledPar_tabu, include dynamically changing tabu list sizes, aspiration criterion and long term memory. A new intensification strategy based on intermediate term memory is proposed and shown to be promising especially while solving large QAPs. The combination of all these elements gives a very efficient heuristic for the QAP: the best known or improved solutions are obtained in a significantly smaller number of iterations than in other comparative studies. Combined with the implementation on CM-2, this approach provides suboptimal solutions to QAPs of bigger dimensions in reasonable time. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|