Random Problems with Added Structure

In the experiments with ternary CSPs we did not detect an advantage of the DE compared to the non-binary representation (and consequently the HVE). MAC in the DE is rarely better than MGAC-2001 (only in some cases of very tight constraints and large domain sizes), despite the use of PW-AC for propagation. Also, while MAC-PW-ACd is competitive and often faster than MGAC-2001 in sparse random problems, this result is reversed as the density increases. A basic reason for these results is that in randomly generated problems (especially ones with ternary constraints) we get many pairs of non-binary constraints that share at most one original variable. It is known (see bcvbw02 for example) that for any such pair of constraints, the filtering achieved by AC in the DE is the same as the filtering achieved by GAC in the non-binary representation (and AC in the HVE). Therefore, AC in the DE ``looses'' much of its filtering power.

To validate this conjecture, we experimented with a generation model where structure is added to purely random problems. To be precise, we experimented with problems where a clique of variables is embedded in a randomly generated instance. For ternary problems any two constraints in the clique may share one or two variables. This is decided at random. For 4-ary problems any two constraints in the clique may share one, or two, or three variables. Again, this is decided at random. Table 3 compares the performance of various MAC algorithms on $<30,10,3,5,*>$ and $<20,10,4,1,*>$ problems of this type. For the second class we only include results for MAC-PW-ACd, which is by far the best algorithm for such problems, and MGAC-2001.

Table 3: Average cpu times of MAC algorithms for the DE and the double encoding and MGAC for the non-binary representation of random problems with embedded cliques. All times are in seconds. Each number gives the average of 50 instances from around the phase transition region.

	arity			clique size			MGAC-2001			MAC-2001			MAC-PW-AC			MAC-2001d			MAC-PW-ACd
	3			0			633.50			45303.76			9205.95			7549.61			1362.31
	3			10			874.07			21007.45			5349.55			3078.45			421.07
	3			20			1121.39			1932.49			389.22			392.08			65.81
	3			30			1598.87			374.03			48.22			102.30			5.02
	4			0			90.11												106.04
	4			10			247.18												61.12
	4			20			8348.92												322.86

As we can see, the comparative results of the algorithms vary according to the size of the embedded clique. When there is no clique embedded (clique size=0) MGAC-2001 is faster than the algorithms for the binary encodings. As the clique size grows, the binary encodings, and especially the double, become more efficient. The double encoding is more effective than the DE for all clique sizes. For a large clique that covers all variables, MAC in the double encoding is many orders of magnitude faster than MGAC-2001. This huge difference is caused by the presence of many constraints that share more than one variable in the non-binary representation. In such cases filtering through the constraints between dual variables is very strong. However, much of this advantage is lost when generic algorithms are used in the encodings. Similar results occur in denser problems when this generation model is used.