Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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 (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.

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

Open Access in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 24 downloads
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

urn-nbn

Altmetric score

urn-nbn
Total: 19 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf