solved efficiently by each of our heuristics, instances in the phase-transition region can be extremely hard. For the instances of the general model, most path-consistent instances are also consistent. Conversely, path-consistency is a bad approximation to consistency for instances of the hard model. These instances are also much harder to solve than instances of the general model.

When comparing the different heuristics, we found that the heuristics using one of the maximal tractable subsets as a split set are not as much faster in deciding consistency of RSAT instances as their theoretical advantage given by the reduced average branching factor and the resulting exponentially smaller size of the sear space indicates. This is because using path-consistency as a forward checking method considerably reduces the search space in all cases.  Nevertheless, using one of the maximal tractable subsets as a split set, in particular H 8 , still leads to a much faster solution and solves more instances in reasonable time than the other heuristics. Although the two maximal tractable subsets Q 8 and C 8 contain more relations than H s , their average branching factor is lower, i.e., when using H s one has to decompose more relations (256 - 148 = 108) than when using the other two sets (96 and 98 relations, respectively), but H R splits the relations better than the other two sets.  Most relations can be decomposed into only two H s sub-relations, while many relations must be decomposed into three C 8 sub-relations or into three Q 8 sub-relations.

This explains the superior performance of heuristics involving H s for decomposition.

Among the instances we generated, we stored those which could not be solved by all heuristics within a maximum number of 10,000 visited nodes in the search space in order to find out how the different heuristics perform on these hard instances. We found that almost all hard instances are located in the phase-transition region and that there are many more hard instances in the hard model than in the general model. We orthogonally combined all heuristics and ran them on all hard instances. This turned out to be very successful. Apart from one instance, all hard instances of the general model could be solved, most of them with a very low number of visited nodes. The hard instances of the hard model were much more difficult: many of them could not be solved by any of the heuristics. Nevertheless, many more instances were solved by orthogonally combining the heuristics than by each heuristic alone. Again, most of them were solved using a low number of visited nodes.

Based on our observations on orthogonally combining different heuristics, we tried to identify the combination of heuristics which is most successful in efficiently solving many instances and used this combination for solving very large instances. It turned out that the best combination involves only heuristics which use maximal tractable subsets for decomposition. With this combination we were able to solve almost all randomly generated instances of the phase-transition region of the general model up to a size of n = 500 regions very efficiently.  This seems to be impossible when considering the enormous size of the search space, which is on average 1039323 for instances of size n = 500 when using H s as a split set.

Our results show that despite its NP-hardness, we were able to solve almost all randomly generated RSAT instances of the general model efficiently. This is neither due to the low number of different RCC-8 relations (instances generated according to the hard model are very hard in the phase-transition region) nor to our generation procedure for random instances which does not lead to trivially flawed instances asymptotically. It is mainly due to the maximal tractable subsets which cover a large fraction of RCC-8 and which lead