Extending a Generic Constraint Solver over Polymorphic Data

No Thumbnail Available
Journal Title
Journal ISSN
Volume Title
Helsinki University of Technology | Diplomityö
Checking the digitized thesis and permission for publishing
Instructions for the author
Date
2005
Major/Subject
Tietojenkäsittelyteoria
Mcode
T-119
Degree programme
Language
en
Pages
9+59
Series
Abstract
Rajoiteohjelmointia 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.
Description
Supervisor
Niemelä, Ilkka
Thesis advisor
Huima, Antti
Keywords
constraint, rajoite, constraint propagation, rajoitteidenvyörytys, lattice, hila, linear inequality, lineaarinen epäyhtälö, tuple (string), merkkijono
Other note
Citation