Complementary Approaches to Constraint Satisfaction

01.09.2004 - 31.12.2006
Research funding project
Many important problems in artificial intelligence, data base systems, and operations research can be formulated as constraint satisfaction problems (CSPs). Although solving a CSP is computationally hard in general, many of the problems that arise in practice have special properties that allow them to be solved efficiently. The question of identifying restrictions to the general problem that are sufficient to ensure tractability is important from both a practical and a theoretical point of view. In this project we will pursue the theoretical and practical investigation of two complementary approaches for the efficient solution of CSPs: bounded hypertree-width and bounded maximum deciency. The first approach generalizes the concept of acyclic CSPs, i.e., CSPs with (nearly) acyclic constraint hypergraphs. The second approach generalizes boolean satisfiability problems which can be solved by (nearly) perfect matchings of their associated incidence graphs. Major goals of the project include the development of new algorithms for constraint solving based on the complementary approaches, the implementation of parallel exact algorithms and of sequential heuristic algorithms for hypertree decomposition, and the practical and theoretical evaluation of the new algorithms by benchmark problems of practical relevance.

People

Project leader

Project personnel

Institute

Grant funds

  • FWF - Österr. Wissenschaftsfonds (National) Austrian Science Fund (FWF)

Research focus

  • Computational Intelligence: 100%

Keywords

GermanEnglish
zuordnungs-basierte Methodenmatching-based methods
Hyperbaum Zerlegunghypertree decompostion

Publications