Komplementäre Ansätze für Constraint Satisfaction

01.09.2004 - 31.12.2006
Research funding project
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 SCPs im allgemeinen komputational sehr aufwändig ist, habe 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. Diese 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 este 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.

People

Project leader

Project personnel

Institute

Förderungmittel

  • FWF - Österr. Wissenschaftsfonds (National) Fonds zur Förderung der wissenschaftlichen Forschung (FWF)

Research focus

  • Computational Intelligence: 100%

Keywords

GermanEnglish
zuordnungs-basierte Methodenmatching-based methods
Hyperbaum Zerlegunghypertree decompostion

Publications