Global constraints in distributed CSP: Concurrent GAC and explanations in ABT

Mohamed Wahbi; Kenneth N. Brown

doi:10.1007/978-3-319-10428-7_52

Global constraints in distributed CSP: Concurrent GAC and explanations in ABT

Mohamed Wahbi
, Kenneth N. Brown

University College Cork

Research output: Chapter in Book/Report/Conference proceedings › Conference proceeding › peer-review

Abstract

The expressiveness of Distributed CSP has been recently enhanced to include global constraints. Careful reformulation of contractible global constraints has been shown to improve efficiency. In this paper, we first show that explained global constraints further improves the efficiency in distributed problems, sometimes by over two orders of magnitude. We then propose maintaining GAC concurrently for any global constraint, without reformulation. We show empirically that concurrent GAC significantly reduces both message passing and computation time, achieving an order of magnitude improvement on some distributed meeting scheduling problems.

Original language	English
Title of host publication	Principles and Practice of Constraint Programming - 20th International Conference, CP 2014, Proceedings
Publisher	Springer Verlag
Pages	721-737
Number of pages	17
ISBN (Print)	9783319104270
DOIs	https://doi.org/10.1007/978-3-319-10428-7_52
Publication status	Published - 2014
Event	20th International Conference on the Principles and Practice of Constraint Programming, CP 2014 - Lyon, France Duration: 8 Sep 2014 → 12 Sep 2014

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8656 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	20th International Conference on the Principles and Practice of Constraint Programming, CP 2014
Country/Territory	France
City	Lyon
Period	8/09/14 → 12/09/14

Access to Document

10.1007/978-3-319-10428-7_52

Cite this

Wahbi, M., & Brown, K. N. (2014). Global constraints in distributed CSP: Concurrent GAC and explanations in ABT. In Principles and Practice of Constraint Programming - 20th International Conference, CP 2014, Proceedings (pp. 721-737). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8656 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-10428-7_52

Wahbi, Mohamed ; Brown, Kenneth N. / Global constraints in distributed CSP : Concurrent GAC and explanations in ABT. Principles and Practice of Constraint Programming - 20th International Conference, CP 2014, Proceedings. Springer Verlag, 2014. pp. 721-737 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{409c09e5d5eb46b4bfd27872190b6b12,

title = "Global constraints in distributed CSP: Concurrent GAC and explanations in ABT",

abstract = "The expressiveness of Distributed CSP has been recently enhanced to include global constraints. Careful reformulation of contractible global constraints has been shown to improve efficiency. In this paper, we first show that explained global constraints further improves the efficiency in distributed problems, sometimes by over two orders of magnitude. We then propose maintaining GAC concurrently for any global constraint, without reformulation. We show empirically that concurrent GAC significantly reduces both message passing and computation time, achieving an order of magnitude improvement on some distributed meeting scheduling problems.",

author = "Mohamed Wahbi and Brown, \{Kenneth N.\}",

year = "2014",

doi = "10.1007/978-3-319-10428-7\_52",

language = "English",

isbn = "9783319104270",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "721--737",

booktitle = "Principles and Practice of Constraint Programming - 20th International Conference, CP 2014, Proceedings",

address = "Germany",

note = "20th International Conference on the Principles and Practice of Constraint Programming, CP 2014 ; Conference date: 08-09-2014 Through 12-09-2014",

}

Wahbi, M & Brown, KN 2014, Global constraints in distributed CSP: Concurrent GAC and explanations in ABT. in Principles and Practice of Constraint Programming - 20th International Conference, CP 2014, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8656 LNCS, Springer Verlag, pp. 721-737, 20th International Conference on the Principles and Practice of Constraint Programming, CP 2014, Lyon, France, 8/09/14. https://doi.org/10.1007/978-3-319-10428-7_52

Global constraints in distributed CSP: Concurrent GAC and explanations in ABT. / Wahbi, Mohamed; Brown, Kenneth N.
Principles and Practice of Constraint Programming - 20th International Conference, CP 2014, Proceedings. Springer Verlag, 2014. p. 721-737 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8656 LNCS).

Research output: Chapter in Book/Report/Conference proceedings › Conference proceeding › peer-review

TY - GEN

T1 - Global constraints in distributed CSP

T2 - 20th International Conference on the Principles and Practice of Constraint Programming, CP 2014

AU - Wahbi, Mohamed

AU - Brown, Kenneth N.

PY - 2014

Y1 - 2014

N2 - The expressiveness of Distributed CSP has been recently enhanced to include global constraints. Careful reformulation of contractible global constraints has been shown to improve efficiency. In this paper, we first show that explained global constraints further improves the efficiency in distributed problems, sometimes by over two orders of magnitude. We then propose maintaining GAC concurrently for any global constraint, without reformulation. We show empirically that concurrent GAC significantly reduces both message passing and computation time, achieving an order of magnitude improvement on some distributed meeting scheduling problems.

AB - The expressiveness of Distributed CSP has been recently enhanced to include global constraints. Careful reformulation of contractible global constraints has been shown to improve efficiency. In this paper, we first show that explained global constraints further improves the efficiency in distributed problems, sometimes by over two orders of magnitude. We then propose maintaining GAC concurrently for any global constraint, without reformulation. We show empirically that concurrent GAC significantly reduces both message passing and computation time, achieving an order of magnitude improvement on some distributed meeting scheduling problems.

UR - https://www.scopus.com/pages/publications/84906213176

U2 - 10.1007/978-3-319-10428-7_52

DO - 10.1007/978-3-319-10428-7_52

M3 - Conference proceeding

AN - SCOPUS:84906213176

SN - 9783319104270

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 721

EP - 737

BT - Principles and Practice of Constraint Programming - 20th International Conference, CP 2014, Proceedings

PB - Springer Verlag

Y2 - 8 September 2014 through 12 September 2014

ER -

Wahbi M, Brown KN. Global constraints in distributed CSP: Concurrent GAC and explanations in ABT. In Principles and Practice of Constraint Programming - 20th International Conference, CP 2014, Proceedings. Springer Verlag. 2014. p. 721-737. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-10428-7_52

Global constraints in distributed CSP: Concurrent GAC and explanations in ABT

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this