Table 1 shows the performance, measured in cpu time, of the algorithms on five classes of randomly generated CSPs. All classes are from the hard phase transition region. Classes 1, 2, 3, and 4 are sparse, while 5 is more dense. We do not include results on MHAC2001 because experiments showed that this algorithm has very similar behavior to MHAC2001. The reason is that, because of the nature of the constraints, the dom/deg heuristic almost always selects original variables for instantiation. In the rare cases where the heuristic selected dual variables, this resulted in a large increase in cpu time.

From Table 1 we can see that MHAC2001 performs better than MGAC2001 on the sparse problems. In general, for all the 3ary classes we tried with density less than the relative run time performance of MHAC2001 compared to MGAC2001 ranged from being equal to being around 23 times faster. In the very sparse class 4, which includes problems with 5ary constraints, MHAC2001 is considerably more efficient than MGAC2001. This is due to the fact that for sparse problems with relatively large domain sizes the hard region is located at low constraint looseness (i.e. small domains for dual variables) where only a few operations are required for the revision of dual variables. Another factor contributing to the dominance of the binary algorithm in class 4 is the larger arity of the constraints. The nonbinary algorithm requires more operations to check the validity of tuples when the tuples are of large arity, as explained in Section 3.1.
When the density of the graph increases (class 5), the overhead of revising the domains of dual variables and restoring them after failed instantiations slows down MHAC2001, and as a result it is outperformed by MGAC2001. For denser classes than the ones reported, the phase transition region is at a point where more than half of the tuples are allowed, and in such cases the nonbinary algorithm performs even better.
Nikolaos Samaras 20051109