Proceedings

A Fast and Simple Algorithm for Bounds Consistency of the AllDifferent Constraint

Download BibTeX Cite

Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. Pages 245-249.

© 2003 International Joint Conferences on Artificial Intelligence

Abstract

In constraint programming one models a problem by stating constraints on acceptable solutions. The constraint model is then usually solved by interleaving backtracking search and constraint propagation. Previous studies have demonstrated that designing special purpose constraint propagators for commonly occurring constraints can significantly improve the efficiency of a constraint programming approach. In this paper we present a fast, simple algorithm for bounds consistency propagation of the alldifferent constraint. The algorithm has the same worst case behavior as the previous best algorithm but is much faster in practice. Using a variety of benchmark and random problems, we show that our algorithm outperforms existing bounds consistency algorithms and also outperforms-on problems with an easily identifiable property-state-ofthe-art commercial implementations of propagators for stronger forms of local consistency.

  1. [Gabow and Tarjan, 1985] H. N. Gabow and R. E. Tarjan. A linear-time algorithm for a special case of disjoint set union. JCSS, 30(2):209-221, 1985.
  2. [Gent and Walsh, 1999] I. P. Gent and T. Walsh. CSPlib: A benchmark library for constraints. In CP-99, pp. 480-481 .
  3. [!LOGS. A., 1998] !LOG Solver 4.2 user's manual, 1998.
  4. [Leconte, 1996] M. Leconte. A bounds-based reduction scheme for constraints of difference. In Proc. of the Constraint-96 Int '/ Workshop on Constraint-Based Rea- soning, pp. 19-28, Key West, Florida, 1996.
  5. [L6pez-Ortiz eta!., 2003] A. L6pez-Ortiz, C. G. Quimper, J. Tromp and P. van Beek. Faster practical algorithms for the all-diff constraint. Technical Report, CS-2003-05, School of Computer Science, University of Waterloo, 2003.
  6. [Mehlhorn and Thiel, 2000] K. Mehlhorn and S. Thiel. Faster algorithms for bound-consistency of the sortedness and alldifferent constraint. In CP-2000, pp. 306-319.
  7. [Puget, 1998] J.-F. Puget. A fast algorithm for the bound consistency of alldiff constraints. AAAI-98, pp. 359-366.
  8. [Regin, 1994] J.-C. Regin. A filtering algorithm for con- straints of difference in CSPs. In AAAI-94, pp. 362-367.
  9. [Schulte and Stuckey, 2001] C. Schulte and P. J. Stuckey. When do bounds and domain propagation lead to the same search space. In PPDP-2001, pp. 115-126.
  10. [Smith eta/., 2000] B. M. Smith, K. Stergiou, and T. Walsh. Using auxiliary variables and implied constraints to model non-binary problems. In AAAI-2000, pp. 182-187.
  11. [Stergiou and Walsh, 1999] K. Stergiou and T. Walsh. The difference all-difference makes. In JJCAJ-99, pp. 414-419. IJCAI
  12. [van Hoeve, 2001] W. J. van Hoeve. The alldifferent con- straint: A survey. Submitted manuscript. Available from http:/ /www.cwi.nlrwjvhlpapers/alldiff.pdf, 2001. Link

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards