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.

Design Space Exploration (DSE) is the exploration of a space of possible designs with the goal of finding some optimal design according to some constraints and criteria. Within embedded systems design, automated DSE in particular can allow the system designer to efficiently find good solutions in highly complex design spaces. One particular tool for performing automated DSE is IDeSyDe which uses Constraint Programming (CP) and constraint optimization for modelling and optimization. The constraint models of DSE often include some real-valued parameters, but optimized CP-solvers typically require integer arguments. This makes it necessary to discretize the problem in order to make the approach useful in practice, effectively limiting the size of the search space significantly. The effects of this discretization procedure on the quality of the solutions have not previously been well studied. An investigation into how this kind of discretization affects the approximate solutions could make the approach more rigorous, and possibly also uncover exploitable details that could facilitate the development of even more efficient algorithms. This project presents a convergence proof based in CP and Multiresolutional analysis (MRA), including a practically useful error bound for solutions obtained with different discretizations. In particular, the mapping and scheduling of Syncronous Data Flow (SDF) models for streaming applications onto tile-based multiple processor system-on-chip platforms with a common time-division multiplexing bus interconnect is studied. The theoretical results are also verified using IDeSyDe for a few different configurations of applications and platforms. It can be seen that the experiments behave as predicted, with first order convergence in total error and adherence to the bound. / Designrymdsutforskning är benämningen för en systematisk utforskning av en rymd av möjliga designer i syfte att hitta bra eller optimala lösningar som optimerar något mål och som uppfyller krav och begränsningar. Automatiserad designrymdsutforskning har i synnerhet sett utveckling för tillämpningar inom design av inbyggda system, där den ständigt ökande komplexiteten hos moderna plattformar motiverat utvecklingen av nya metoder. Två stora delar är nödvändiga för att kunna tillämpa designrymdsutforskning för design av inbyggda system: en modell av systemet och en optimiseringsprocess. Beroende på situation kan systemmodeller variera från detaljerade simuleringar på transistornivå till övergripande analytiska modeller på applikationsnivå eller högre. Detaljerade simuleringar gör det möjligt att utvärdera en viss lösning mycket noggrant, men till en hög beräkningskostnad. Med analytiska modeller är det istället billigt att utvärdera enskilda lösningar, men på bekostnad av noggrannhet. På samma sätt kan olika optimeringsprocesser också användas: snabbare approximativa algoritmer kan användas för att hitta lösningar relativt snabbt men utan garantier för optimalitet, medans mer uttömmande algoritmer typiskt kräver mycket beräkningskraft. Ett verktyg för automatiserad designrymdsutforskning är IDeSyDe. IDeSyDe använder villkorsbaserade modeller och uttömmande sökning genom Branch and Bound. Optimerade algoritmiska lösare för villkorsprogrammeringsproblem kräver ofta heltalsparametrar. Modeller för designrymdsutforskning innehåller å andra sidan ofta kontinuerliga parametrar. På grund av detta är det ofta nödvändigt att disktretisera problemet för att effektivt kunna hitta lösningar. Eftersom en diskretisering begränsar mängden lösningar i sökrymden riskerar en sådan omformulering att ta bort även optimala lösningar. En designrymdsutforskningsalgoritm som utnyttjar diskretisering av designrymden måste på grund av detta generellt ses som en approximativ algoritm. Hur en sådan diskretisering påverkar lösningarna -- dvs. hur nära de approximativa lösningarna kan förväntas komma den optimala lösningen utan diskretisering -- har dock inte studerats i närmare detalj. En bättre förståelse för hur diskreta, approximativa problem och lösningar relaterar till sina exakta motsvarigheter kan ge metoden mer rigör. En undersökning av den underliggande matematiken har också potential att belysa andra samband och strukturer som potentiellt skulle kunna användas för att utveckla bättre eller mer effektiva algoritmer. I den här rapporten presenteras ett konvergensbevis baserat på villkorsprogrammering och multiupplösningsanalys med ett begränsat felintervall i termer av probleminstansspecifika parametrar och en diskretiseringsparameter. Beviset är framtaget för tillämpning med IDeSyDe och är därför begränsat till en kombination av modeller som verktyget för närvarande stödjer, nämligen strömmande-dataflödesapplikationer beskrivna som synkrona dataflödesmodeller (Synchronous Data Flow, SDF) samt en ''tile''-baserad modell för system med flera processorer på ett chip (MPSoC) med en gemensam tidspartitionerad multiplexor-bus för kommunikation mellan processor-''tiles''. De teoretiska resultaten är verifierade och tillämpade på ett flertal exempelfall beräknade med IDeSyDe, där konvergensen studerats experimentellt.

The Planning And Scheduling (PLAS) module of ICE (Intelligent Control Environment) is responsible for planning and scheduling a large fleet of vehicles. This process involves the creation of tasks to be executed by the vehicles. Using this information, PLAS decides which vehicles should execute which tasks, which are modelled as constraint satisfaction problems. Solving the constraint satisfaction problems is slow. To improve efficiency, a number of different techniques exist. One of these is arc consistency, that entails taking a constraint satisfaction problem and evaluating its variables pairwise by applying the constraints among them. Using arc consistency, we can discern the candidate solutions to constraint satisfaction problems faster than doing a pure search. In addition, arc consistency allows us to detect and act early on inconsistencies in constraint satisfaction problems. The work in this master thesis includes the implementation of a constraint solver for symbolic constraints, containing the arc consistency algorithm AC3. Furthermore, it encompasses the implementation of a constraint satisfaction problem generator, based on the Erdős-Rényi graph model, inspired by the quasigroup completion problem with holes, that allows the evaluation of the constraint solver on large-sized problems. Using the constraint satisfaction problem generator, a set of experiments were performed to evaluate the constraint solver. Furthermore, a set of complementary scenarios using manually created constraint satisfaction problems were performed to augment the experiments. The results show that the performance scales up well. / Schemaläggningsmodulen PLAS som är en del av ICE (Intelligent Control Environment) är ansvarig för planering och schemaläggning av stora mängder fordonsflottor. Denna process involverar skapandet av uppgifter som behöver utföras av fordonen. Utifrån denna information bestämmer PLAS vilka fordon som ska utföra vilka uppgifter, vilket är modellerat som villkorsuppfyllelseproblem. Att lösa villkorsuppfyllelseproblem är långsamt. För att förbättra prestandan, så finns det en mängd olika tekniker. En av dessa är bågkonsekvens, vilket involverar att betrakta ett villkorsuppfyllelseproblem och utvärdera dess variabler parvis genom att tillämpa villkoren mellan dem. Med hjälp av bågkonsekvens kan vi utröna kandidatlösningar för villkorsuppfyllelseproblemen snabbare, jämfört med ren sökning. Vidare, bågkonsenvens möjliggör upptäckande och bearbetning av inkonsekvenser i villkorsuppfyllelseproblem. Arbetet i denna masteruppsats omfattar genomförandet av en villkorslösare för symboliska villkor, innehållandes bågkonsekvensalgoritmen AC3. Vidare, så innefattar det genomförandet av en villkorsuppfyllelseproblemgenerator, baserad på grafmodellen Erdős-Rényi, inspirerad av kvasigruppkompletteringsproblem med hål, villket möjliggör utvärdering av villkorslösaren på stora problem. Med hjälp av villkorsuppfyllelseproblemgeneratorn så utfördes en mängd experiment för att utvärdera villkorslösaren. Vidare så kompletterades experimenten av en mängd scenarion utförda på manuellt skapade villkorsuppfyllelseproblem. Resultaten visar att prestandan skalar upp bra.