FM Paul Saikko väittelee maanantaina 2.12.2019 klo 12 Helsingin yliopiston Exactum-rakennuksen auditoriossa B123 (Pietari Kalmin katu 5, 1. kerros) aiheesta Implicit Hitting Set Algorithms for Constraint Optimization. Vastaväittäjänä toimii professori Laurent Simon (University of Bordeaux, Ranska) ja kustoksena apulaisprofessori Matti Järvisalo (Helsingin yliopisto). Väitöstilaisuus pidetään englanniksi.
Paul Saikon väitöskirjatyö on osa Helsingin yliopiston tietojenkäsittelytieteen osastolla ja Constraint Reasoning and Optimization -ryhmässä tehtävää tutkimusta. Väitöskirjatyön ohjaajina ovat toimineet apulaisprofessori Matti Järvisalo ja professori Petri Myllymäki (Helsingin yliopisto).
Implisiittisiin osumajoukkoihin perustuvia rajoiteoptimointimenetelmiä
Käytännön sovellutuksista kumpuavat optimointiongelmat ovat usein laskennallisesti haastavia. Deklaratiiviset menetelmät tarjoavat keskeisen tavan lähestyä erinäisiä laskennallisesti haastavia optimointiongelmia. Deklaratiivisissa lähestymistavoissa ratkaistavana oleva ongelma mallinnetaan yleisesti matemaattisina rajoitteina siten, että alkuperäisen ongelman instanssien rajoitekuvauksen rajoitteet voidaan toteuttaa, jos ja vain jos ongelmainstanssille on olemassa ratkaisu. Ratkaisujen löytäminen rajoitekuvaukselle edellyttää yleisten algoritmisten ratkaisumenetelmien kehittämistä rajoitekuvauskielille.
Tässä väitöskirjassa kehitetään uudentyyppisiä käytännöllisiä eksakteja deklaratiivisia ratkaisumenetelmiä, jotka pohjautuvat ns. implicit hitting set (IHS) -optimointialgoritmiparadigmaan. Erityisesti työssä kehitetään ja toteutetaan IHS-pohjaisia menetelmiä neljälle laskennallisesti haastavalle, tekoälytutkimuksen näkökulmasta motivoidulle NP-kovalle optimointiongelmalle: lauselogiikan optimointilaajennukselle (MaxSAT), keskeiselle epämonotonisen päättelyn lähestymistavalle (answer set optimization, ASP), lauseloogiselle abduktiolle, sekä optimaalisten kausaaliverkkojen löytämisongelmalle. Työssä kehitetään sekä yleisiä että ongelmakohtaisia hakutekniikoita IHS-kontekstissa, kehitetään avoimen lähdekoodin implementaatioita ja osoitetaan empiriisten evaluaatioiden kautta näiden olevan käytännössä varteenotettavia vaihtoehtoja kunkin ongelman tehokkaaseen ratkaisemiseen.
Väitöskirjan saatavuus
Väitöskirjan elektroninen versio on saatavilla Helsingin yliopiston e-thesis-palvelussa osoitteessa http://urn.fi/URN:ISBN:978-951-51-5669-3.
Painettuja väitöskirjoja voi tiedustella väittelijältä itseltään: paul.saikko@cs.helsinki.fi.