[Zurück]


Diplom- und Master-Arbeiten (eigene und betreute):

I. Ivezic:
"Extending the gecode framework with interval constraint programming";
Betreuer/in(nen): G. Raidl, L. Di Gaspero; Institut für Computergraphik und Algorithmen, 2012; Abschlussprüfung: 10/2012.



Kurzfassung deutsch:
Die vorliegende Arbeit führt den Leser zunüchst in die Grundlagen von Constraint Programming
sowie hierfür relevante Konzepte wie Suchräume, Variablen, ihre Domänen und Constraints ein.
Weiters wird beschrieben wie reale Probleme als Constraint Satisfaction Modelle dargestellt und
gelöst werden können. Grundprinzipien wie Constraint Propagation und die Baumsuche werden
skizziert.
Interval Constraint Programming ist eine Unterklasse von Constraint Programming, in der
die Domänen der Variablen Intervalle sind. Um diese näher zu betrachten werden zunächst die
Grundlagen der Intervall-Arithmetik vorgestellt. Danach wird auf Besonderheiten der Interval
Constraint Satisfaction Probleme eingegangen. Neben Konsistenzbegriffen wie Knoten- und Bogenkonsistenz
haben nun Hüllen- und Boxkonsistenzen eine große Bedeutung. Algorithmen um
die beiden letztgenannten Konsistenzen zu erreichen werden im Detail beschrieben. Gecode
ist eine C++ Constraint Programming Entwicklungsumgebung, für die in dieser Diplomarbeit
entsprechende Erweiterungen für Inverval Constraint Programming entwickelt wurden. Für die
Intervallarithmetik wurde hierfür auf die Boost-Library sowie SymbolicC++ zurückgegriffen.
Die implementierte Erweiterung wurde auf verschiedenen skalierbaren Benchmark-Instanzen
getestet, nämlich Broyden Banded, Broyden Tridiagonal und Brown. Jede dieser Benchmark-
Instanzen hat spezielle Eigenschaften. Die Experimente mit Broyden Banded zeigen, dass SymbolicC++
eine Schwachstelle der Erweiterung sein könnte, weil es zu langen Constraint - Initialisierungszeiten
führt. Broyden Tridiagonal wertet im Speziellen die Leistung der Boxkonsistenz,
während Brown primär die Leistung in Bezug auf die Hüllenkonsistenz aufzeigt. Weiters wurde
die Erweiterung auf einem komplexeren 3D-Rekonstruktionsproblem erfolgreich getestet.

Kurzfassung englisch:
This thesis introduces the reader to the basics of constraint programming, including the main
concepts such as search space, variables and their domains, and constraints. Furthermore, the
constraint satisfaction problem modeling process, and the general procedure required to solve it
is introduced. Constraint satisfaction problem solving concepts such as propagation and branching
are explained for a general constraint satisfaction problem as well.
Interval constraint programming, a subclass of constraint programming where the domains
of variables in the problems are intervals, is then introduced. Then, basic concepts of interval
arithmetic needed for interval constraint programming are shown. Afterwards, the peculiarities
of interval constraint satisfaction problems, as opposed to general constraint satisfaction
problems are highlighted. Furthermore, generic consistency notions, namely, node and arc consistency
are introduced. They are followed with the description of hull consistency and box
consistency, which are the two consistency notions relevant to interval constraint programming.
A method for enforcing both hull and box consistency is given in detail.
The C++ constraint programming framework Gecode is then briefly presented. An extension
of Gecode supporting interval constraint programming, that was developed alongside this thesis,
is described in detail. The implementation relies on the Boost Interval library to handle intervals.
To implement the box consistency propagator, an additional library, namely, SymbolicC++ was
used, and had to be extended as well. The necessary extensions of SymbolicC++ library are
described as well.
The implemented extension was tested on various scalable benchmarks, namely Broyden
Banded, Broyden Tridiagonal and Brown, each having its unique properties testing, and highlighting
a particular feature of the system. Experiments on Broyden Banded show that SymbolicC++
may have been a suboptimal choice for the extension, as it suffers from relatively high
constraint initialization time. Broyden Tridiagonal evaluates the performance of box consistency
propagation, whereas Brown evaluates hull consistency propagators.
The final test of the extension is the 3D reconstruction problem. The formal description of
the problem is given, and the results of the 3D reconstruction obtained with the extension are
shown, both statistically and graphically.


Elektronische Version der Publikation:
http://publik.tuwien.ac.at/files/PubDat_213074.pdf


Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.