A Parallel Tabu Search Alglorithm for the Quadratic Assignment Problem
Samuel Gabrielsson · 2008
A parallel version of the tabu search algorithm is implemented and used to optimize the solutions for a quadratic assignment problem (QAP). The instances are taken from the qaplib website (http://www.opt.math.tu-graz.ac.at/qaplib/) and we mainly concentrate on optimizing the instances announced by Sergio Carvalho derived from the ``Microarray Placement Problem'' (http://gi.cebitec.uni-bielefeld.de/comet/chiplayout/qap) where one wants to find an arrangement of the probes (small DNA fragments) on specific locations of a microarray chip. We briefly explain combinatorics including graph theory and also the theory behind combinatorial optimization, heuristics and metaheuristcs. A description of some network optimization problems are also introduced before we apply our parallel tabu search algorithm to the quadratic assignment problem. Different approaches like Boltzmann selection procedure and random restarts are used to optimize the solutions. Through our experiments, we show that our parallel version of tabu Search do indeed manage to further optimize and even find better solutions found so far in the litterature. We try out a communication protocol based on sequentially generating graphs, where each node in the graph corresponds to a CPU or tabu search thread. One of the main goals is to find out if communication helps to further optimize the best known solution found so far for each instace.