On forward checking for non-binary constraint satisfaction

Christian Bessière; Pedro Meseguer; Eugene C. Freuder; Javier Larrosa

doi:10.1007/978-3-540-48085-3_7

On forward checking for non-binary constraint satisfaction

Christian Bessière
, Pedro Meseguer
, Eugene C. Freuder
, Javier Larrosa

School of Computer Science and Information Technology

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

Abstract

Solving non-binary constraint satisfaction problems, a crucial challenge for the next years, can be tackled in two different ways: translating the non-binary problem into an equivalent binary one, or extending binary search algorithms to solve directly the original problem. The latter option raises some issues when we want to extend definitions written for the binary case. This paper focuses on the well-known forward checking algorithm, and shows that it can be generalized to several non-binary versions, all fitting its binary definition. The classical version, proposed by Van Hentenryck, is only one of these generalizations.

Original language	English
Title of host publication	Principles and Practice of Constraint Programming – CP 1999 - 5th International Conference, CP 1999, Proceedings
Editors	Joxan Jaffar
Publisher	Springer Verlag
Pages	88-102
Number of pages	15
ISBN (Print)	3540666265, 9783540666264
DOIs	https://doi.org/10.1007/978-3-540-48085-3_7
Publication status	Published - 1999
Event	5th International Conference on Principles and Practice of Constraint Programming, CP 1999 - Alexandria, United States Duration: 11 Oct 1999 → 14 Oct 1999

Publication series

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

Conference

Conference	5th International Conference on Principles and Practice of Constraint Programming, CP 1999
Country/Territory	United States
City	Alexandria
Period	11/10/99 → 14/10/99

Access to Document

10.1007/978-3-540-48085-3_7

Cite this

Bessière, C., Meseguer, P., Freuder, E. C., & Larrosa, J. (1999). On forward checking for non-binary constraint satisfaction. In J. Jaffar (Ed.), Principles and Practice of Constraint Programming – CP 1999 - 5th International Conference, CP 1999, Proceedings (pp. 88-102). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1713). Springer Verlag. https://doi.org/10.1007/978-3-540-48085-3_7

Bessière, Christian ; Meseguer, Pedro ; Freuder, Eugene C. et al. / On forward checking for non-binary constraint satisfaction. Principles and Practice of Constraint Programming – CP 1999 - 5th International Conference, CP 1999, Proceedings. editor / Joxan Jaffar. Springer Verlag, 1999. pp. 88-102 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{29b27d0ae6d84dfe81600c718b8872a9,

title = "On forward checking for non-binary constraint satisfaction",

abstract = "Solving non-binary constraint satisfaction problems, a crucial challenge for the next years, can be tackled in two different ways: translating the non-binary problem into an equivalent binary one, or extending binary search algorithms to solve directly the original problem. The latter option raises some issues when we want to extend definitions written for the binary case. This paper focuses on the well-known forward checking algorithm, and shows that it can be generalized to several non-binary versions, all fitting its binary definition. The classical version, proposed by Van Hentenryck, is only one of these generalizations.",

author = "Christian Bessi{\`e}re and Pedro Meseguer and Freuder, \{Eugene C.\} and Javier Larrosa",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1999.; 5th International Conference on Principles and Practice of Constraint Programming, CP 1999 ; Conference date: 11-10-1999 Through 14-10-1999",

year = "1999",

doi = "10.1007/978-3-540-48085-3\_7",

language = "English",

isbn = "3540666265",

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

publisher = "Springer Verlag",

pages = "88--102",

editor = "Joxan Jaffar",

booktitle = "Principles and Practice of Constraint Programming – CP 1999 - 5th International Conference, CP 1999, Proceedings",

address = "Germany",

}

Bessière, C, Meseguer, P, Freuder, EC & Larrosa, J 1999, On forward checking for non-binary constraint satisfaction. in J Jaffar (ed.), Principles and Practice of Constraint Programming – CP 1999 - 5th International Conference, CP 1999, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1713, Springer Verlag, pp. 88-102, 5th International Conference on Principles and Practice of Constraint Programming, CP 1999, Alexandria, United States, 11/10/99. https://doi.org/10.1007/978-3-540-48085-3_7

On forward checking for non-binary constraint satisfaction. / Bessière, Christian; Meseguer, Pedro; Freuder, Eugene C. et al.
Principles and Practice of Constraint Programming – CP 1999 - 5th International Conference, CP 1999, Proceedings. ed. / Joxan Jaffar. Springer Verlag, 1999. p. 88-102 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1713).

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

TY - GEN

T1 - On forward checking for non-binary constraint satisfaction

AU - Bessière, Christian

AU - Meseguer, Pedro

AU - Freuder, Eugene C.

AU - Larrosa, Javier

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1999.

PY - 1999

Y1 - 1999

N2 - Solving non-binary constraint satisfaction problems, a crucial challenge for the next years, can be tackled in two different ways: translating the non-binary problem into an equivalent binary one, or extending binary search algorithms to solve directly the original problem. The latter option raises some issues when we want to extend definitions written for the binary case. This paper focuses on the well-known forward checking algorithm, and shows that it can be generalized to several non-binary versions, all fitting its binary definition. The classical version, proposed by Van Hentenryck, is only one of these generalizations.

AB - Solving non-binary constraint satisfaction problems, a crucial challenge for the next years, can be tackled in two different ways: translating the non-binary problem into an equivalent binary one, or extending binary search algorithms to solve directly the original problem. The latter option raises some issues when we want to extend definitions written for the binary case. This paper focuses on the well-known forward checking algorithm, and shows that it can be generalized to several non-binary versions, all fitting its binary definition. The classical version, proposed by Van Hentenryck, is only one of these generalizations.

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

U2 - 10.1007/978-3-540-48085-3_7

DO - 10.1007/978-3-540-48085-3_7

M3 - Conference proceeding

AN - SCOPUS:84957380785

SN - 3540666265

SN - 9783540666264

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

SP - 88

EP - 102

BT - Principles and Practice of Constraint Programming – CP 1999 - 5th International Conference, CP 1999, Proceedings

A2 - Jaffar, Joxan

PB - Springer Verlag

T2 - 5th International Conference on Principles and Practice of Constraint Programming, CP 1999

Y2 - 11 October 1999 through 14 October 1999

ER -

Bessière C, Meseguer P, Freuder EC, Larrosa J. On forward checking for non-binary constraint satisfaction. In Jaffar J, editor, Principles and Practice of Constraint Programming – CP 1999 - 5th International Conference, CP 1999, Proceedings. Springer Verlag. 1999. p. 88-102. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-48085-3_7

On forward checking for non-binary constraint satisfaction

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this