|
|
|
Hypertree Complementary Approaches to Constraint
Satisfaction |
|
Many
important problems in artificial intelligence, database 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 deficiency. 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. This project is supported by the
Austrian Science Fund (FWF) project: Nr. P17222-N04, Complementary Approaches
to Constraint Satisfaction (Project time: Sept. 2004-2006). |
|
2006 © Database and
Artificial Intelligence Group, Vienna
University of Technology |