Hypertree

Complementary Approaches to Constraint Satisfaction

Home Members Publications Software downloads Work Progress

Project Goals

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