Using stochastic methods to guide search in CLP: A preliminary report

Abstract

Recently Lee, Stuckey and Tam have shown the advantages of incorporating stochastic solvers into constraint logic programming (CLP) systems. Their approaches, while efficient, both suffer from some form of incompleteness and complication in semantics. This paper proposes a generalization of these previous efforts by using stochastic methods to guide and speed up the search of derivation trees for successful branches. By spending computational effort to exercise the stochastic solver at various nodes in the derivation tree, additional information is obtained to suggest (a) delaying exploration of unpromising subtrees and (b) visiting promising children first. Using these simple guidelines we give two example search strategies extending the basic depth-first search procedure used typically in CLP systems. Each extension exhibits a different degree of interaction and cooperation between the principal CLP solver and the stochastic solver. While encompassing all previous integration schemes, the generality of our framework also opens up myriad possibilities for using a stochastic solver to improve search efficiency. Last but not least, since the interaction is through the search strategy most semantic properties of constraint logic programming are inherited.

This project is supported in part by a CUHK Direct Grant, ARC Small Grant S4969494, and a University of Melbourne Young Asian Scholar Grant.