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 MHAC-2001- because experiments showed that this algorithm has very similar behavior to MHAC-2001. 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 MHAC-2001 performs better than MGAC-2001 on the sparse problems. In general, for all the 3-ary classes we tried with density less than the relative run time performance of MHAC-2001 compared to MGAC-2001 ranged from being equal to being around 2-3 times faster. In the very sparse class 4, which includes problems with 5-ary constraints, MHAC-2001 is considerably more efficient than MGAC-2001. 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 non-binary 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 MHAC-2001, and as a result it is outperformed by MGAC-2001. 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 non-binary algorithm performs even better.
Nikolaos Samaras 2005-11-09