Résumé
In practice, constraint satisfaction problems are often structured. By exploiting this structure, solving algorithms can make important gains in performance. In this paper, we focus on structured continuous CSPs defined by systems of equations. We use graph decomposition techniques to decompose the constraint graph into a directed acyclic graph of small blocks. We present new algorithms to solve decomposed problems which solve the blocks in partial order and perform intelligent backtracking when a block has no solution
For under-constrained problems, the solution space can be explored by choosing some variables as input parameters. However, in this case, the decomposition is no longer unique and some choices lead to decompositions with smaller blocks than others. We present an algorithm for selecting the input parameters that lead to good decompositions
First experimental results indicate that, even on small problems, significant speedups can be obtained using these algorithms.