Extending a Generic Constraint Solver over Polymorphic Data

Simple item page
dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.advisorHuima, Antti 
dc.contributor.authorAho, Pauli
dc.contributor.departmentTietotekniikan osastofi
dc.contributor.schoolTeknillinen korkeakoulufi
dc.contributor.schoolHelsinki University of Technologyen
dc.contributor.supervisorNiemelä, Ilkka 
dc.date.accessioned2020-12-04T19:23:18Z
dc.date.available2020-12-04T19:23:18Z
dc.date.issued2005 
dc.description.abstractRajoiteohjelmointia tutkitaan aktiivisesti monipuolisen soveltuvuutensa ansiosta. Tässä diplomityössä esitellään yleinen rajoiteohjelmointijärjestelmä nimeltä Conformiq Constraint Solver (CMIQCS) rajoiteongelmien ratkaisujen etsimiseen. Järjestelmä hyödyntää polymorfista hilaa, joka approksimoi ääretöntä boolen arvojen, symbolien, rationaalilukujen ja monikkojen tietotyyppien määrittelyjoukkoa. Järjestelmä käyttää rajoitteidenvyörytystä ja jakamista. Jonkin tietyn tyypin ongelmien ratkaisuun tarkoitetut erityismenetelmät suoriutuvat usein paremmin kuin yleiset menetelmät, jotka hyödyntävät eri hakutekniikoita ja hakuavaruuden rajaamista. Ensimmäisenä tavoitteena on sisällyttää CMIQCS:än erityismenetelmä, joka ratkaisee lineaarisia epäyhtälöryhmiä. Fourier-Motzkin -eliminaatio sopii tarkoitukseen, koska se antaa ratkaisujoukon eksplisiittisessä muodossa. Algoritmin vaikutusta CMiQCS:n suorituskykyyn mitataan ja analysoidaan. Järjestelmästä puuttuu lisäksi kyky liittää kaksi monikkoa yhteen, joten toinen tavoite liittyy monikkohilan parantamiseen määrittelyjoukkohilassa. Jokainen monikko muodostetaan laajennetun deterministisen äärellisen automaatin avulla siten, että automaattiin lisätään priorisoidut siirtymät ja siirtymille annetaan indeksit. Työssä tarkastellaan uuden hilan tärkeimpiä operaatioita ja indeksikonstruktion käyttökelpoisuutta arvioidaan testien avulla.fi
dc.format.extent9+59 
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/92636
dc.identifier.urnURN:NBN:fi:aalto-2020120451471
dc.language.isoenen
dc.programme.majorTietojenkäsittelyteoriafi
dc.programme.mcodeT-119fi
dc.rights.accesslevelclosedAccess
dc.subject.keywordconstrainten
dc.subject.keywordrajoitefi
dc.subject.keywordconstraint propagationen
dc.subject.keywordrajoitteidenvyörytysfi
dc.subject.keywordlatticeen
dc.subject.keywordhilafi
dc.subject.keywordlinear inequalityen
dc.subject.keywordlineaarinen epäyhtälöfi
dc.subject.keywordtuple (string)en
dc.subject.keywordmerkkijonofi
dc.titleExtending a Generic Constraint Solver over Polymorphic Dataen
dc.titlePolymorfista tietoa hyödyntävän yleisen rajoiteratkaisimen laajentaminenfi
dc.type.okmG2 Pro gradu, diplomityö 
dc.type.ontasotMaster's thesisen
dc.type.ontasotPro gradu -tutkielmafi
dc.type.publicationmasterThesis 
local.aalto.digiauthask
local.aalto.digifolderAalto_03028
local.aalto.idinssi28850
local.aalto.openaccessno
Files
Collections
[dipl] Teknillinen korkeakoulu / TKK