Extending a Generic Constraint Solver over Polymorphic Data

Thumbnail Image

URL

Journal Title

Journal ISSN

Volume Title

Helsinki University of Technology | Master's thesis
Checking the digitized thesis and permission for publishing
Instructions for the author
Location:
P1 Ark Aalto

Authors

Date

2005

Department

Tietotekniikan osasto

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

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-2020120451471

Collections

[dipl] Teknillinen korkeakoulu / TKK