Ivezić, I. (2012). Extending the Gecode framework with interval constraint programming [Diploma Thesis, Technische Universität Wien]. reposiTUm. http://hdl.handle.net/20.500.12708/160590
E186 - Institut für Computergraphik und Algorithmen
-
Date (published):
2012
-
Number of Pages:
72
-
Keywords:
interval constraint programming; gecode; 3d reconstruction
de
interval constraint programming; gecode; 3d rekonstruktion
en
Abstract:
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.
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 areshown, both statistically and graphically.