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 / 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.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-175851 |
| Date | January 2015 |
| Creators | From, Anton |
| Publisher | KTH, Skolan för informations- och kommunikationsteknik (ICT) |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-ICT-EX ; 2015:75 |
Page generated in 0.0022 seconds