Random Problems

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-$full$ 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.

Table 1: Comparison of algorithms MGAC-2001 and MHAC-2001 on random classes of problems. Classes 1 and 2 taken from the paper by Bessiére et al. bmfl99. We give the average run times (in seconds) for 100 instances at each class. The ``winning'' time for each instance is given in bold. We follow this in the rest of the paper.

	class			MGAC-2001			MHAC-2001
	1: $<30,6,3,1.847,50>$			2.08			1.90
	2: $<75,5,3,0.177,41>$			4.09			3.41
	3: $<50,20,3,0.3,5>$			64.15			28.10
	4: $<50,10,5,0.001,0.5>$			74.72			22.53
	5: $<20,10,3,5,40>$			5.75			8.15

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 $3\%-4\%$ 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.