Change search
ReferencesLink to record
Permanent link

Direct link
A parallel tabu search alglorithm for the quadratic assignment problem
2008 (English)Independent thesis Advanced level (professional degree), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

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 ( and we mainly concentrate on optimizing the instances announced by Sergio Carvalho derived from the ``Microarray Placement Problem'' ( 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.

Place, publisher, year, edition, pages
Keyword [en]
Physics Chemistry Maths, Parallel Tabu Search, Optimization, QAPLIB, heuristics, metaheuristics
Keyword [sv]
Fysik, Kemi, Matematik
URN: urn:nbn:se:ltu:diva-43798ISRN: LTU-EX--08/019--SELocal ID: 1a0d96e0-082a-4424-a973-d35a43f97b4aOAI: diva2:1017040
Subject / course
Student thesis, at least 30 credits
Educational program
Computer Science and Engineering, master's level
Validerat; 20101217 (root)Available from: 2016-10-04 Created: 2016-10-04Bibliographically approved

Open Access in DiVA

fulltext(500 kB)0 downloads
File information
File name FULLTEXT01.pdfFile size 500 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

ReferencesLink to record
Permanent link

Direct link