Related Work

Although, the DE was proposed in 1989 [Dechter PearlDechter Pearl1989] and the HVE in 1990 [Rossi, Petrie, DharRossi et al.1990], the first substantial effort towards evaluating their efficiency was carried out in 1998 [Bacchus van BeekBacchus van Beek1998]. In that work, Bacchus and van Beek compared theoretically and empirically the FC algorithm in the two encodings against FC for non-binary CSPs. Also, they introduced FC+, a specialized algorithm for the HVE. The algorithms compared by Bacchus and van Beek were the simplest versions of FC; hFC0 and hFC1 (i.e. FC+) for the HVE, and nFC0 for the non-binary representation. We extend that work by studying various recent and more advanced versions of FC.

Following Bacchus and van Beek bvb98, Stergiou and Walsh made a theoretical and empirical study of AC in the encodings [Stergiou WalshStergiou Walsh1999]. It was proved that AC in the HVE is equivalent to GAC in the non-binary representation, while AC in the DE is stronger. In the small experimental study included in the paper by Stergiou & Walsh sw99, MAC for the HVE, DE, and double encoding was compared to MGAC in the non-binary representation of some crossword puzzles and Golomb rulers problems. Results showed an advantage for the non-binary representation and the HVE, but it is important to note that all the MAC algorithms used generic inefficient algorithms to enforce AC.

Smith, Stergiou & Walsh ssw00 performed a more extensive experimental comparison of MAC in the HVE and the double encoding, and MGAC in a non-binary model of the Golomb rulers problem. However, again the MAC algorithms in the encodings used a generic algorithm to enforce AC. As a result they were outperformed by MGAC in the non-binary model.

Beacham et al. bcsvB01 compared the performances of different models, heuristics, and algorithms for CSPs using crossword puzzle generation problems as benchmarks. Among the models that were compared was the HVE, the DE and the non-binary representation. Once again, the algorithms that were applied in the encodings were generic algorithms. For example, two of the implemented algorithms for the DE were MAC that uses AC-3 for propagation and MAC that uses AC-7. Both these algorithms suffer from the very high complexity of AC propagation. As demonstrated, the use of algorithm PW-AC for propagation can significantly enhance the performance of MAC in crossword puzzle problems.

Bacchus et al. bcvbw02 presented an extensive theoretical study of the DE and the HVE. Among other results, polynomial bounds were placed on the relative performance of FC and MAC in the two encodings and the non-binary representation, or it was shown that no polynomial bound exists. For example, it was shown that FC in the HVE (i.e. hFC0 in the terminology we use) is never more than a polynomial factor worse than FC in the DE, but FC in the DE can be exponentially worse than FC in the HVE. Also, FC in the non-binary representation (i.e. nFC0 in the terminology we use) can be exponentially worse than FC in the HVE, and vice versa. We add to these results by analyzing the performance of various more advanced algorithms for the HVE and the double encoding.

Smith modelled the problem of finding a maximum density stable pattern ``still-life'' in Conway's game of Life using MAC in the double encoding with remarkable success, compared to other constraint programming and integer programming approaches [SmithSmith2002]. The MAC algorithm was implemented using the Table constraint of ILOG Solver. This constraint implements the generic AC algorithm of Bessiére & Régin br97, which is very expensive when used in the DE because of its high time complexity. We believe that the results presented by Smith can be further improved if MAC-PW-AC is used instead.