TY - JOUR
T1 - A reactive and hybrid constraint solver
AU - Monfroy, Eric
AU - Castro, Carlos
AU - Crawford, Broderick
AU - Soto, Ricardo
AU - Paredes, Fernando
AU - Figueroa, Christian
N1 - Funding Information:
This work was partially funded by the TIC Amsud project TODAS, the INRIA-CONICYT project CoreWeb, the INRIA Associated Team WanaWeb, and the Centro Cientifico-Tecnologico de Valparaiso (CCTVal), FB0821.
PY - 2013/3/1
Y1 - 2013/3/1
N2 - In Castro et al. [Castro, C., Monfroy, E., Figueroa, C., and Meneses, R. (2005), An Approach for Dynamic Split Strategies in Constraint Solving, in Proceedings of MICAI 2005 (Vol. 3789), LNAI, Berlin: Springer, pp. 162-174] a framework for adaptive enumeration strategies and meta-backtracks for a propagation-based constraint solver has been studied. Here, we extend this framework in order to trigger some functions of a solver, or of a hybrid solver to respond to some observations of the solving process. We can also simply design adaptive hybridisation strategies by just changing some rules of the update component of our framework. We experiment with this framework on a hybrid Branch and Bound + propagation solver in which propagation can be triggered w.r.t. some observations of the solving process. The results show that some phases of propagation are not only beneficial to the Branch and Bound algorithm, but also that propagation is too costly to be executed at each node of the search tree. The hybridisation strategies are thus crucial in order to decide when to perform the or not propagation.
AB - In Castro et al. [Castro, C., Monfroy, E., Figueroa, C., and Meneses, R. (2005), An Approach for Dynamic Split Strategies in Constraint Solving, in Proceedings of MICAI 2005 (Vol. 3789), LNAI, Berlin: Springer, pp. 162-174] a framework for adaptive enumeration strategies and meta-backtracks for a propagation-based constraint solver has been studied. Here, we extend this framework in order to trigger some functions of a solver, or of a hybrid solver to respond to some observations of the solving process. We can also simply design adaptive hybridisation strategies by just changing some rules of the update component of our framework. We experiment with this framework on a hybrid Branch and Bound + propagation solver in which propagation can be triggered w.r.t. some observations of the solving process. The results show that some phases of propagation are not only beneficial to the Branch and Bound algorithm, but also that propagation is too costly to be executed at each node of the search tree. The hybridisation strategies are thus crucial in order to decide when to perform the or not propagation.
KW - autonomous search
KW - constraint solving
KW - hybrid solver
KW - reactive search
UR - http://www.scopus.com/inward/record.url?scp=84873578768&partnerID=8YFLogxK
U2 - 10.1080/0952813X.2012.656328
DO - 10.1080/0952813X.2012.656328
M3 - Article
AN - SCOPUS:84873578768
VL - 25
SP - 1
EP - 22
JO - Journal of Experimental and Theoretical Artificial Intelligence
JF - Journal of Experimental and Theoretical Artificial Intelligence
SN - 0952-813X
IS - 1
ER -