Constraint solving for model-based engineering applications using relational aggregation

Abstract

Starting with a thorough requirements analysis and based on relational aggregation, this dissertation thesis develops a concise framework for solving heterogeneous constraints. These constraints are typical for engineering applications. The framework implements the classical services; checking for a constraint problem's consistency and solving all variables. Furthermore, it provides new algorithms for obtaining minimal conflicts and minimal explanations (for all findings) and proves the respective correctness theorems. Based on aggregation strategies, the connection to the well-known hypertree decomposition is made. Besides solving one constraint problem, a further focus is on solving large sequences of similar problems, as e.g. typical for model-based diagnosis, by efficient reuse facilities. The theoretical part of the dissertation is complemented by pseudocode for an object-oriented implementation of the framework. The document closes with some screenshots of a prototypic implementation in Java and a variety of experimental results.

Diese Dissertation entwickelt - beginnend mit einer detaillierten Anforderungsanalyse und basierend auf relationaler Aggregation - eine durchgängige Methodik zur Verarbeitung von heterogenen Constraints wie sie typischerweise im Engineering auftreten. Neben den klassischen Diensten wie der Untersuchung der Konsistenz eines Constraint Problems und dem Lösen aller Variablen werden neue Algorithmen zur Berechnung minimaler Konflikte bzw. minimaler Beweise (für gefundene Lösungen) vorgestellt und deren Korrektheit bewiesen. Ausgehend von Aggregationsstrategien wird die Verbindung zur bekannten Hypertree Dekomposition für Constraint Probleme hergestellt. Neben der Behandlung eines Constraint Problems wird durch effiziente reuse Mechanismen das sequentielle Lösen vieler ähnlicher Probleme, wie z.B. bei der modellbasierten Diagnose, unterstützt. Der theoretische Teil der Dissertation wird komplettiert durch Pseudocode für eine objekt-orientierte Implementierung der gesamten Methodik. Screenshots einer prototypischen Implementierung in Java und experimentelle Ergebnisse schließen die Dissertation ab.