×

zbMATH — the first resource for mathematics

Generalised arc consistency for the AllDifferent constraint: an empirical survey. (English) Zbl 1184.68472
Summary: The AllDifferent constraint is a crucial component of any constraint toolkit, language or solver, since it is very widely used in a variety of constraint models. The literature contains many different versions of this constraint, which trade strength of inference against computational cost. In this paper, we focus on the highest strength of inference, enforcing a property known as generalised arc consistency (GAC). This work is an analytical survey of optimizations of the main algorithm for GAC for the AllDifferent constraint. We evaluate empirically a number of key techniques from the literature. We also report important implementation details of those techniques, which have often not been described in published papers. We pay particular attention to improving incrementality by exploiting the strongly-connected components discovered during the standard propagation process, since this has not been detailed before. Our empirical work represents by far the most extensive set of experiments on variants of GAC algorithms for AllDifferent. Overall, the best combination of optimizations gives a mean speedup of 168 times over the same implementation without the optimizations.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aggoun, Abderrahamane; Chan, David; Dufresne, Pierre; Falvey, Eamon; Grant, Hugh; Harvey, Warwick; Herold, Alexander; Macartney, Geoffrey; Meier, Micha; Miller, David; Mudambi, Shyam; Novello, Stefano; Perez, Bruno; van Rossum, Emmanuel; Schimpf, Joachim; Shen, Kish; Tsahageas, Periklis Andreas; de Villeneuve, Dominique Henry, Eclipse user manual release 5.10, 2006
[2] Alt, H.; Blum, N.; Mehlhorn, K.; Paul, M., Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1.5} \sqrt{m / \log n})\), Information processing letters, 37, 4, 237-240, (1991) · Zbl 0714.68036
[3] Berge, Claude, Graphs and hypergraphs, (1973), North-Holland Publishing Company · Zbl 0254.05101
[4] Carlsson, Mats; Schulte, Christian, Finite domain constraint programming systems, 2002, Available from
[5] Simon Colton, Ian Miguel, Constraint generation via automated theory formation, in: Proceedings of the Seventh International Conference on Principles and Practice of Constraint Programming, 2001, pp. 575-579 · Zbl 1067.68622
[6] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L., Introduction to algorithms, (1990), MIT Press · Zbl 1158.68538
[7] Costa, Marie-Christine, Persistency in maximum cardinality bipartite matchings, Operations research letters, 15, 3, 143-149, (1994) · Zbl 0810.90126
[8] Eppstein, David, Implementation of hopcroft-karp algorithm in python, 2002
[9] Ian P. Gent, Chris Jefferson, Ian Miguel, Minion: A fast, scalable, constraint solver, in: Proceedings 17th European Conference on Artificial Intelligence (ECAI 2006), 2006, pp. 98-102
[10] Ian P. Gent, Chris Jefferson, Ian Miguel, Watched literals for constraint propagation in minion, in: Proceedings 12th International Conference on the Principles and Practice of Constraint Programming (CP 2006), 2006
[11] Ian P. Gent, Christopher Jefferson, Ian Miguel, Peter Nightingale, Data structures for generalised arc consistency for extensional constraints, in: Proceedings of the Twenty Second Conference on Artificial Intelligence (AAAI-07), 2007, pp. 191-197
[12] Ian P. Gent, Ian Miguel, Andrea Rendl, Tailoring solver-independent constraint models: A case study with essence’ and minion, in: Proceedings of SARA, 2007, pp. 184-199
[13] Hnich, Brahim; Miguel, Ian; Gent, Ian P.; Walsh, Toby, Csplib: A problem library for constraints
[14] Hopcroft, J.E.; Karp, R.M., An \(n^{2.5}\) algorithm for maximum matchings in bipartite graphs, SIAM journal on computing, 2, 4, 225-231, (1973) · Zbl 0266.05114
[15] ILOG Solver 6.0 User Manual, ILOG S.A., 2003
[16] Katriel, Irit, Expected-case analysis for delayed filtering, (), 119-125 · Zbl 1177.68190
[17] Henry A. Kautz, Yongshao Ruan, Dimitris Achlioptas, Carla P. Gomes, Bart Selman, Mark E. Stickel, Balance and filtering in structured satisfiable problems, in: Proceedings of IJCAI-2001, 2001, pp. 351-358 · Zbl 0985.90509
[18] Knuth, D.E.; Raghunathan, A., The problem of compatible representatives, SIAM journal of discrete mathematics, 5, 3, 422-427, (1992) · Zbl 0825.68494
[19] Mikael Z. Lagerkvist, Christian Schulte, Advisors for incremental propagation, in: Proceedings 13th Principles and Practice of Constraint Programming (CP 2007), 2007, pp. 409-422
[20] Claude-Guy Quimper, Toby Walsh. The all different and global cardinality constraints on set, multiset and tuple variables, in: Recent Advances in Constraints, LNAI, vol. 3419, 2006 · Zbl 1180.68249
[21] Jean-Charles Régin, A filtering algorithm for constraints of difference in CSPs, in: Proceedings 12th National Conference on Artificial Intelligence (AAAI 94), 1994, pp. 362-367
[22] Schulte, Christian; Stuckey, Peter J., Speeding up constraint propagation, (), 619-633 · Zbl 1152.68583
[23] Schulte, Christian; Tack, Guido, Views and iterators for generic constraint implementations, (), 118-132 · Zbl 1180.68103
[24] João C. Setubal, New experimental results for bipartite matching, in: Proceedings of netflow93, Technical Report TR-21/93, Dipartamento de Informatica, Università di Pisa, 1993, pp. 211-216
[25] João C. Setubal, Sequential and parallel experimental results with bipartite matching algorithms, Technical Report EC-96-09, Institute of Computing, University of Campinas, Brasil, 1996
[26] Kostas Stergiou, Toby Walsh, The difference all-difference makes, in: Proceedings IJCAI’99, 1999
[27] Tarjan, Robert, Depth-first search and linear graph algorithms, SIAM journal on computing, 1, 2, 146-160, (1972) · Zbl 0251.05107
[28] Willem-Jan van Hoeve, The alldifferent constraint: A survey, in: Proceedings Sixth Annual Workshop of the ERCIM Working Group on Constraints, 2001 · Zbl 1152.68595
[29] Wallace, Mark, Practical applications of constraint programming, Constraints, 1, 1/2, 139-168, (1996)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.