Komplementäre Ansätze für Constraint Satisfaction

Viele wichtige Probleme in den Bereichen Artificial Intelligence, Datenbank Systemen und in Operations Research lassen sich direkt als sogenannte Constraint Satisfaction Problems (CSPs) formulieren. Obwohl das Lösen von CSPs im allgemeinen komputational sehr aufwendig ist, haben viele Probleme, die sich in der Praxis stellen, Eigenschaften, die eine effiziente Lösung ermöglichen. Die Identifikation solcher Eigenschaften ist sowohl von praktischer, als auch von theoretischer Bedeutung. Dieses Projekt widmet sich der praktischen und theoretischen Erforschung zweier komplementärer Ansätze zur effizienten Lösung von CSPs: beschränkte Hyperbaumweite und beschränkter maximaler Defekt. Der erste Ansatz verallgemeinert das Konzept der azyklischen CSPs. Der zweite Ansatz verallgemeinert boolsche Erfüllbarkeitsprobleme (SAT), die mittels Zuordnungen (matchings) in den dazugehörigen Inzidenzgraphen effizient gelöst werden können. Hauptziele des Projekts beinhalten die Entwicklung neuer Algorithmen zur Lösung von CSPs (basierend auf den beiden komplementären Ansätzen und deren Kombination), die Entwicklung und Implementierung paralleler exakter und sequentieller heuristischer Algorithmen zur Hyperbaumzerlegung, sowie die praktische und theoretische Auswertung der neuen Algorithmen mittels Vergleichstests auf praxisrelevanten Problemklassen.

Viele wichtige Probleme der Künstlichen Intelligenz, der Datenbank Theorie und des Operationsresearch lassen sich als Constraint Satisfaction Probleme formulieren. Solche Probleme gibt es unter anderem in der Planung, Konfiguration, Diagnose, in computerunterstütztem Sehen, in räumlichem und temporärem Schließen, Graphentheorie, usw. Obwohl Constraint Satisfaction Probleme im Allgemeinen NP-vollständig sind, haben viele dieser Probleme in der Praxis zusätzliche Eigenschaften, die es ermöglichen, sie doch effizient zu lösen. Hyperbaumzerlegungen von Hypergraphen ist ein Maß für die Zyklizität von Hypergraphen. Constraint Satisfaction Probleme, deren Problem-Hypergraph eine beschränkte Hyperbaumweite hat, lassen sich effizient lösen. Die wichtigsten Ziele des Projekts "Complementary Approaches to Constraint Satisfaction" waren, Algorithmen zu entwerfen, die effizient eine Hyperbaumzerlegung für große Constraint Satisfaction Probleme mit möglichst kleiner Hyperbaumweite generieren. Weitere Ziele waren mögliche theoretische Erweiterungen des Konzepts der Hyperbaumzerlegung zu analysieren, sowie die Anwendbarkeit der Methode zu untersuchen. Die Algorithmen, die wir im Rahmen dieses Projektes entwickelt haben, erstellen, verglichen mit anderen Algorithmen aus der Literatur, momentan die effizientesten Hyperbaumzerlegungen. Diese Algorithmen tragen dazu bei, dass man in der Zukunft Constraint Satisfaction Probleme mit kleiner Hyperbaumweite noch effizienter lösten kann. Weiters haben wir ein allgemeineres Maß für die Zyklizität von Hypergraphen, die sogenannte generalisierte Hyperbaumweite, untersucht. Auf der einen Seite erzeugen unsere Algorithmen nicht nur Hyperbaumzerlegungen, sondern gleichzeitig auch generalisierte Hyperbaumzerlegungen, auf der anderen Seite, haben unsere theoretische Untersuchungen gezeigt, dass das Entscheidungsproblem für beschränkte generalisierte Hyperbraumweite ein NP- vollständiges Problem ist. Für dieses Resultat haben die Autoren den "Best Paper Award" bei PODS`2007 erhalten. Nachdem wir die Quellen der Komplexität identifiziert hatten, haben wir eine neue Zerlegungsmethode definieren können, die eine effiziente Enscheidungsmethode aufweist, aber trotzdem allgemeiner ist, als alle andere Methoden mit dieser Eigenschaft aus der Literatur. Wir haben auch Quantifizierte Constraint Satisfaction Probleme (QCSP) studiert. Wir konnten uns ein klares Bild über die Eigenschaften machen, die es ermöglichen, dass QCSPs mit strukturellen Einschränkungen effizient gelöst werden können. Die Methoden für Hyperbaumzerlegungen haben eine zentrale Rolle gespielt, neue Algorithmen für verwandten Probleme zu entwerfen. Wir haben effiziente Algorithmen für die Suche von reinen Nash Equilibria in bestimmten strategischen Spielen gefunden, sowie für die Core-Berechnung für das Data Exchange Problem.