A reactive and hybrid constraint solver

Eric Monfroy, Carlos Castro, Broderick Crawford, Ricardo Soto, Fernando Paredes, Christian Figueroa

Research output: Contribution to journalArticlepeer-review

32 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)1-22
Number of pages22
JournalJournal of Experimental and Theoretical Artificial Intelligence
Volume25
Issue number1
DOIs
StatePublished - 1 Mar 2013
Externally publishedYes

Keywords

  • autonomous search
  • constraint solving
  • hybrid solver
  • reactive search

Fingerprint

Dive into the research topics of 'A reactive and hybrid constraint solver'. Together they form a unique fingerprint.

Cite this