More Web Proxy on the site http://driver.im/

Article

A Parallel Algorithm for GAC Filtering of the Alldifferent Constraint

Authors:

Wijnand Suijlen,

Félix de Framond,

Arnaud Lallouet,

Antoine PetitetAuthors Info & Claims

Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 19th International Conference, CPAIOR 2022, Los Angeles, CA, USA, June 20-23, 2022, Proceedings

Pages 390 - 407

https://doi.org/10.1007/978-3-031-08011-1_26

Published: 20 June 2022 Publication History

Abstract

In constraint programming the Alldifferent constraint is one of the oldest and most used global constraints. The algorithm by Régin enforces generalized arc-consistency, which is the strongest level of consistency for a single constraint. It is also the most time consuming despite several optimizations that were developed by others.

This paper parallelizes the Alldifferent generalized arc-consistent filtering algorithm, which is one of the first attempts for any global constraint. It does so by using a parallel graph search algorithm for two major parts of Régin’s algorithm: finding a maximum matching and finding the strongly connected components. Most effective known optimizations are also ported. Experiments solving a large N-queens problem or a resource constrained scheduling problem show that generalized arc-consistent filtering can be significantly sped-up on a 64-core shared-memory system and on a 200-core distributed-memory system. We discuss also several scenarios where this algorithm should be applied or not.

References

[1]

AMD: Memory population guidelines for AMD EPYC processors. Tech. Rep. 56301, revision 1.1, Advanced Micro Devices (2018)

[2]

Azad A, Buluç A, and Pothen A Computing maximum cardinality matchings in parallel on bipartite graphs via tree-grafting IEEE Trans. Parallel Distrib. Syst. 2016 28 1 44-59

[3]

Bessiere C, Narodytska N, Quimper C-G, and Walsh T Achterberg T and Beck JC The alldifferent constraint with precedences Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems 2011 Heidelberg Springer 36-52

[4]

Bisseling, R.H.: Parallel Scientific Computing: A Structured Approach Using BSP. 2nd edn. Oxford University Press (2020)

[5]

Blelloch, G.E., Gu, Y., Shun, J., Sun, Y.: Parallelism in randomized incremental algorithms. In: Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, p. 467–478. SPAA 2016, Association for Computing Machinery, NY (2016).

[6]

Briggs P and Torczon L An efficient representation for sparse sets ACM Lett. Program. Lang. Syst. 1993 2 1–4 59-69

[7]

Campeotto F, Dal Palù A, Dovier A, Fioretto F, and Pontelli E Flatt M and Guo H-F Exploring the use of GPUs in constraint solving Practical Aspects of Declarative Languages 2014 Cham Springer 152-167

[8]

Cheriyan J and Mehlhorn K Algorithms for dense graphs and networks on the random access computer Algorithmica 1996 15 6 521-549

[9]

Erbas, C., Tanik, M.M.: Generating solutions to the N-queens problem using 2-circulants. Math. Mag. 68(5), 343–356 (1995). http://www.jstor.org/stable/2690923

[10]

Gecode Team: Gecode: generic constraint development environment (2019). http://www.gecode.org

[11]

Gent IP, Miguel I, and Nightingale P Generalised arc consistency for the alldifferent constraint: an empirical survey Artif. Intell. 2008 172 18 1973-2000

[12]

Gent IP et al. A review of literature on parallel constraint solving Theory Pract. Logic Program. 2018 18 5–6 725-758

[13]

Graham RL Bounds on multiprocessing timing anomalies SIAM J. Appl. Math. 1969 17 2 416-429

[14]

Granvilliers L and Hains G A conservative scheme for parallel interval narrowing Inf. Process. Lett. 2000 74 3–4 141-146

[15]

Hamadi Y Optimal distributed arc-consistency Constraints 2002 7 3–4 367-385

[16]

van Hoeve, W.-J.: The alldifferent constraint: a survey. CoRR cs.PL/0105015 (2001). https://arxiv.org/abs/cs/0105015

[17]

van Hoeve, W.-J., Katriel, I.: Global constraints. In: Rossi, F., van Beek, P., Walsh, T. (eds.) Handbook of Constraint Programming, Foundations of Artificial Intelligence, vol. 2, pp. 169–208. Elsevier (2006).

[18]

Hopcroft, J.E., Karp, R.M.: A n5/2 algorithm for maximum matchings in bipartite. In: 12th Annual Symposium on Switching and Automata Theory, SWAT 1971, pp. 122–125 (1971).

[19]

Huawei: Tecal RH2288H v2 rack server v100r002. Tech. rep., Huawei Technologies Co., Ltd. (2013), issue 01

[20]

Kasif S On the parallel complexity of discrete relaxation in constraint satisfaction networks Artif. Intell. 1990 45 3 275-286

[21]

Van Kessel, P., Quimper, C.-G.: Filtering algorithms based on the word-ram model. In: Hoffmann, J., Selman, B. (eds.) Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, 22–26 July 2012, Toronto, Ontario, AAAI Press (2012). http://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/view/5135

[22]

Leconte, M.: A bounds-based reduction scheme for constraints of difference. In: Second International Workshop on Constraint-Based Reasoning, Key West, FL, p. 19–28 (1996)

[23]

López-Ortiz, A., Quimper, C.-G., Tromp, J., van Beek, P.: A fast and simple algorithm for bounds consistency of the alldifferent constraint. In: Gottlob, G., Walsh, T. (eds.) IJCAI-03, Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, Acapulco, 9–15 August 2003, pp. 245–250. Morgan Kaufmann (2003). http://ijcai.org/Proceedings/03/Papers/036.pdf

[24]

Mehlhorn K and Thiel S Dechter R Faster algorithms for bound-consistency of the sortedness and the alldifferent constraint Principles and Practice of Constraint Programming – CP 2000 2000 Heidelberg Springer 306-319

[25]

Nguyen T and Deville Y A distributed arc-consistency algorithm Sci. Comput. Program. 1998 30 1–2 227-250

[26]

Nightingale, P.: Are adjacency lists worthwhile in alldifferent. Tech. rep., Citeseer (2009)

[27]

Puget, J.: A fast algorithm for the bound consistency of alldiff constraints. In: Mostow, J., Rich, C. (eds.) Proceedings of the Fifteenth National Conference on Artificial Intelligence and Tenth Innovative Applications of Artificial Intelligence Conference, AAAI 98, IAAI 98, 26–30 July 1998, Madison, Wisconsin, pp. 359–366. AAAI Press/The MIT Press (1998). http://www.aaai.org/Library/AAAI/1998/aaai98-051.php

[28]

Régin, J.-C.: A filtering algorithm for constraints of difference in csps. In: Hayes-Roth, B., Korf, R.E. (eds.) Proceedings of the 12th National Conference on Artificial Intelligence, Seattle, WA, 31 July–4 August 1994, vol. 1, pp. 362–367. AAAI Press/The MIT Press (1994). http://www.aaai.org/Library/AAAI/1994/aaai94-055.php

[29]

Régin J-C and Malapert A Parallel constraint programming Handbook of Parallel Constraint Reasoning 2018 Cham Springer 337-379

[30]

Rolf, C.C., Kuchcinski, K.: Parallel consistency in constraint programming. In: Arabnia, H.R. (ed.) Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA 2009, Las Vegas, Nevada, 13–17 July 2009, 2 vols, pp. 638–644. CSREA Press (2009)

[31]

Ruiz-Andino, A., Araujo, L., Sáenz-Pérez, F., Ruz, J.J.: Parallel arc-consistency for functional constraints. In: Sagonas, K. (ed.) Proceedings of the International Workshop on Implementation Technology for Programming Languages Based on Logic, held in conjunction with the Joint International Conference and Symposium on Logic Programming, Manchester, UK, 20 June 1998, pp. 86–100 (1998)

[32]

Suijlen, W.J.: BSPonMPI - BSPlib implementation on top MPI (2019). https://github.com/wijnand-suijlen/bsponmpi, version 1.1

[33]

Tarjan RE Depth-first search and linear graph algorithms SIAM J. Comput. 1972 1 2 146-160

[34]

Topcuoglu H, Hariri S, and Wu M Performance-effective and low-complexity task scheduling for heterogeneous computing IEEE Trans. Parallel Distrib. Syst. 2002 13 3 260-274

[35]

Valiant LG A bridging model for parallel computation Commun. ACM 1990 33 8 103-111

[36]

Yzelman AN, Bisseling RH, Roose D, and Meerbergen K MulticoreBSP for C: a high-performance library for shared-memory parallel programming Int. J. Parallel Prog. 2013 42 4 619-642

[37]

Zhang, X., Li, Q., Zhang, W.: A fast algorithm for generalized arc consistency of the alldifferent constraint. In: Lang, J. (ed.) Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, 13–19 July 2018, Stockholm, Sweden, pp. 1398–1403. ijcai.org (2018).

Cited By

Zhen LLi ZLi YLi HElkind E(2023)Eliminating the computation of strongly connected components in generalized arc consistency algorithm for alldifferent constraintProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/228(2049-2057)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/228

Index Terms

A Parallel Algorithm for GAC Filtering of the Alldifferent Constraint
1. Software and its engineering
  1. Software notations and tools

Index terms have been assigned to the content through auto-classification.

Recommendations

Extending SMT solvers with support for finite domain alldifferent constraint

In this paper we consider integration of SMT solvers with the filtering algorithms for the finite domain alldifferent constraint. Such integration makes SMT solvers suitable for solving constraint satisfaction problems with the alldifferent constraint ...
The alldifferent constraint with precedences
CPAIOR'11: Proceedings of the 8th international conference on Integration of AI and OR techniques in constraint programming for combinatorial optimization problems

We propose ALLDIFFPREC, a new global constraint that combines together an ALLDIFFERENT constraint with precedence constraints that strictly order given pairs of variables.We identify a number of applications for this global constraint including ...
A bitwise GAC algorithm for alldifferent constraints
IJCAI '23: Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence

The generalized arc consistency (GAC) algorithm is the prevailing solution for alldifferent constraint problems. The core part of GAC for alldifferent constraints is excavating and enumerating all the strongly connected components (SCCs) of the graph ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 19th International Conference, CPAIOR 2022, Los Angeles, CA, USA, June 20-23, 2022, Proceedings

Jun 2022

458 pages

ISBN:978-3-031-08010-4

DOI:10.1007/978-3-031-08011-1

Editor:
Pierre Schaus
UCLouvain, Louvain-la-Neuve, Belgium

© Springer Nature Switzerland AG 2022.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 20 June 2022

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhen LLi ZLi YLi HElkind E(2023)Eliminating the computation of strongly connected components in generalized arc consistency algorithm for alldifferent constraintProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/228(2049-2057)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/228

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents