performance was v *dom/wdeg* in the variable-oriented implementation of arc consistency.

Finally, we experimentally demonstrated that although *dom/wdeg* is the most efficient conflict-driven heuristic, other conflict-driven heuristics like '*alldel*"
and "*fully assigned*" have the advantage of being less dependent on the revision ordering heuristic used. Hence, the performance of *dom/wdeg* can be less predictable under different revision orderings.

As a future work, we intent to experimentally examine the behavior of the modern variable ordering heuristics, on problems with global constraints. Concerning revision ordering heuristics, we plan to evaluate the inverse arc-oriented heuristics: a dom/wdeg *inverse* and a dom/wcon *inverse*, which favor revising arcs (cij ,xi) such that xj , has small domain size.

## Acknowledgements

We would like to thank the anonymous reviewers of an earlier version of this paper for their constructive comments that helped improve the quality of the paper.

## References

[1] T. Balafoutis and K. Stergiou. Experimental evaluation of modern variable selection strategies in constraint satisfaction problems. In Proceedings of the 15th RCRA workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion. Volume 451 of CEUR Workshop Proceedings., (CEUR-WS.org), 2008.

[2] T. Balafoutis and K. Stergiou. Conflict directed variable selection strategies for constraint satisfaction problems. In *Proceedings of the 6th Hellenic* Conference on Artificial Intelligence (SETN 2010), LNAI 6040, pages 29–
38, 2010.

[3] C. Bessi`ere, A. Chmeiss, and L. Sais. Neighborhood-based variable ordering heuristics for the contraint satisfaction problem. In *Proceedings of the 7th* Conference on Principles and Practice of Constraint Programming (CP2001), pages 61–75, 2001.

[4] C. Bessi`ere, E.C. Freuder, and J.C. R´egin. Using Inference to Reduce Arc Consistency Computation. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-1995), pages 592–599, 1995.

[5] C. Bessi`ere and J.C. R´egin. MAC and combined heuristics: two reasons to forsake FC (and CBJ?). In *Proceedings of the 2nd Conference on Principles and Practice of Constraint Programming (CP-1996)*, pages 61–75, Cambridge MA, 1996.

[6] C. Bessi`ere, J.C. R´egin, R. Yap, and Y. Zhang. An Optimal Coarse-grained Arc Consistency Algorithm. *Artificial Intelligence*, 165(2):165–185, 2005.