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

J. H.M. Lee, H. F. Leung, P. J. Stuckey, V. W.L. Tam, H. W. Won

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

3 Citations (Scopus)

Abstract

Recently Lee, Stuckey and Tam have shown the advantages of incorporating stochastic solvers into constraint logic programming (CLP) systems. Then-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.

Original languageEnglish
Title of host publicationConcurrency and Parallelism, Programming, Networking, and Security - 2nd Asian Computing Science Conference, ASIAN 1996, Proceedings
EditorsJoxan Jaffar, Roland H. C. Yap
PublisherSpringer
Pages43-52
Number of pages10
ISBN (Print)3540620311, 9783540620310
Publication statusPublished - 1 Jan 1996
Externally publishedYes
Event2nd Asian Computing Science Conference on Concurrency and Parallelism, Programming, Networking, and Security, ASIAN 1996 - Singapore, Singapore
Duration: 2 Dec 19965 Dec 1996

Publication series

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

Conference

Conference2nd Asian Computing Science Conference on Concurrency and Parallelism, Programming, Networking, and Security, ASIAN 1996
CountrySingapore
CitySingapore
Period2/12/965/12/96

Cite this