TY - GEN
T1 - Automatic triggering of constraint propagation
AU - Monfroy, Eric
AU - Crawford, Broderick
AU - Soto, Ricardo
N1 - Copyright:
Copyright 2021 Elsevier B.V., All rights reserved.
PY - 2013
Y1 - 2013
N2 - A constraint satisfaction problem requires a value, selected from a given finite domain, to be assigned to each variable in the problem, so that all constraints relating the variables are satisfied. The main feature of any constraint solver is constraint propagation, it embeds any reasoning which consists in explicitly forbidding values or combinations of values for some variables of a problem because a given subset of its constraints cannot be satisfied otherwise. It is very important to apply constraint propagation as efficiently as possible. In this paper, we present a hybrid solver based on a Branch and Bound algorithm combined with constraint propagation to reduce the search space. Some rules trigger constraint propagation based on some observations of the solving process. The results show that is possible to make reasonable use of constraint propagation.
AB - A constraint satisfaction problem requires a value, selected from a given finite domain, to be assigned to each variable in the problem, so that all constraints relating the variables are satisfied. The main feature of any constraint solver is constraint propagation, it embeds any reasoning which consists in explicitly forbidding values or combinations of values for some variables of a problem because a given subset of its constraints cannot be satisfied otherwise. It is very important to apply constraint propagation as efficiently as possible. In this paper, we present a hybrid solver based on a Branch and Bound algorithm combined with constraint propagation to reduce the search space. Some rules trigger constraint propagation based on some observations of the solving process. The results show that is possible to make reasonable use of constraint propagation.
KW - Constraint Satisfaction Problems
KW - Constraint propagation
KW - Constraint solving
UR - http://www.scopus.com/inward/record.url?scp=85099486515&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-39640-3_33
DO - 10.1007/978-3-642-39640-3_33
M3 - Conference contribution
AN - SCOPUS:85099486515
SN - 9783642396397
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 452
EP - 461
BT - Computational Science and Its Applications, ICCSA 2013 - 13th International Conference, Proceedings
PB - Springer Verlag
T2 - 13th International Conference on Computational Science and Its Applications, ICCSA 2013
Y2 - 24 June 2013 through 27 June 2013
ER -