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 an 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.

Many important problems in artificial intelligence, database systems, and operations research can be formulated as constraint satisfaction problems. Such problems include problems in scheduling, planning, configuration, diagnosis, machine vision, spatial and temporal reasoning, theory of graphs and networks, etc. Although solving a constraint satisfaction problem is known to be NP complete in general, many of the problems that arise in practice have special properties that allow them to be solved efficiently. Hypertree decompositions of hypergraphs and the corresponding hypertree width is a measure for the cyclicity and therefore tractability of the constraint satisfaction problems. The instances of such problems are tractable if their corresponding hypergraphs has bounded hypertree width. The main goals of the project "Complementary Approaches to Constraint Satisfaction" were to develop algorithms for the efficient generation of `good` hypertree decompositions for larger instances of constraint satisfaction problems, theoretical investigation on a possible generalization of the concept of hypertree decomposition, and the investigation of the applications of the hypertree decompositions for constraint solving. In this project we developed the state of the art algorithms for hypertree decomposition. The proposed algorithms produce currently the best existing results in the literature for hypertree decompositions. The developed efficient algorithms in this project will make possible in the future more efficient solving of CSPs, which have small hypertree width. We also analyzed a more general measure for the cyclicity for the problem structure of CSPs, namely generalized hypertree width. We can compute not only hypertree decompositions but also generalized hypertree decompositions with our heuristic methods. On the theoretical side, we found that testing whether a hypergraph has bounded generalized hypertree width is a difficult (NP complete) problem. On the way to this result, for which the authors received the "Best Paper Award" at PODS`07, we also answered a longstanding open question about join optimization. By identifying the sources of the intractability, we could define a new decomposition method, which is tractable and strictly more general than other known tractable decomposition methods. We also studied quantified CSPs. We could clear up the picture of tractable cases of quantified CSPs under structural restrictions. The hypertree decomposition techniques played a central role in developing new computational methods in related fields as well. We found efficient and scalable algorithms for computing pure Nash equilibria in certain strategic games and for computing cores for data exchange.