Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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
Parallel Portfolio Search for Gecode
KTH, School of Information and Communication Technology (ICT).
2015 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
Parallel Portföljsökning för Gecode (Swedish)
Abstract [en]

Constraint programming is used to solve hard combinatorial problems in a variety of domains, such as scheduling, networks and bioinformatics. Search for solving these problems in constraint programming is brittle and even slight variations in the problem data or search heuristic used can dramatically affect the runtime. But using portfolios of search engines on several variants of a problem by adding randomness to the heuristic used has been proved to counter this problem. A portfolio is defined as a collection of assets that combined gives it a desired return and risk. Unfortunately not all constraint programming systems have implementations of portfolio search, such as Gecode. Therefore were two portfolio search prototypes, sequential and parallel, designed and implemented for Gecode. The design is not system dependent and could easily be implemented in other constraint programming systems. The design and implementation is tested by both validity and performance tests to ensure its soundness. Validity is tested by finding all possible solutions on a moderately difficult combinatorial problem known as the N-Queens problem. Performance is tested by finding the first solution on a very difficult combinatorial problem known as the Latin Square Completion problem with different numbers of search engines. To compare against the same validity and performance tests were run with just one search engine. Results show that the design and implementation of portfolio search is sound. The parallel variant of portfolio search finds solutions faster with more search engines and outperforms the sequential variant. The sequential variant finds solutions about as fast as running with just one search engine. Successfully designing and implementing portfolio search in Gecode will help researchers and companies who use Gecode to save both time and money as they are now able to find better solutions faster by using this portfolio search. It may also contribute to the research within this area and the continued development of Gecode

Abstract [sv]

Villkorsprogrammering används till att lösa svåra kombinatoriska problem inom en mängd områden, såsom schemaläggning, nätverk och bioinformatik. Men sökning för att lösa dessa problem inom villkorsprogrammering är skör och även små variationer i problemets data eller använd sökheuristik kan dramatiskt påverka körtiden. Men att använda portföljer av sökmotorer på flera varianter av ett problem genom att införa slumpmässighet i sökheuristiken har bevisats kontra detta problem. En poftfölj är definierad som en samling tillgångar som kombinerad ger den en önskvärd avkastning och risk. Olyckligtvis så har inte alla villkorsprogrammeringssystem implementationer av portföljsökning, såsom Gecode. Därför designades och implementerades två portföljsökningsprototyper, sekventiell och parallell, för Gecode. Designen är inte systemberoende och kan enkelt implementeras i andra villkorsprogrammeringssystem. Designen och implementationen är testad av både validitets och prestandatest för att försäkra dess sundhet. Validiteten testas genom att finna alla möjliga lösningar för ett lagom svårt kombinatoriskt problem känt som N-Queens problemet. Prestandan testas genom att finna första lösningen för ett väldigt svårt kombinatoriskt problem känt som Latin Square completion problemet med olika många sökmotorer. För att jämföra mot så kör en ensam sökmotor samma validitets och prestandatest. Resultaten visar att designen och implementationen av portföljsökning är sund. Den parallella varianten av portföljsökning hittar lösningar snabbare med fler sökmotorer och överträffar den sekventiella varianten. Den sekventiella varianten hittar lösningar ungefär lika snabbt som en ensam sökmotor. Att framgångsrikt designa och implementera portföljsökning i Gecode kommer hjälpa forskare och företag som använder Gecode att spara både tid och pengar när de nu kan hitta bättre lösningar snabbare genom att använda denna portföljsökning. Det kan också bidra till forskningen inom det här området och den fortsatta utvecklingen av Gecode.

Place, publisher, year, edition, pages
2015.
Series
TRITA-ICT-EX, 2015:75
Keyword [en]
Constraint programming, Gecode, Parallel portfolio search
Keyword [sv]
Villkorsprogrammering, Gecode, Parallel portföljsökning
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-175851OAI: oai:DiVA.org:kth-175851DiVA: diva2:862693
Examiners
Available from: 2015-10-23 Created: 2015-10-23 Last updated: 2017-06-14Bibliographically approved

Open Access in DiVA

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

By organisation
School of Information and Communication Technology (ICT)
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 5 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: 65 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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