Adaptive filtering strategy for numerical constraint satisfaction problems

Araya I.; Soto R.; Crawford B.

dc.contributor.author	Araya I.
dc.contributor.author	Soto R.
dc.contributor.author	Crawford B.
dc.date.accessioned	2020-09-02T22:12:24Z
dc.date.available	2020-09-02T22:12:24Z
dc.date.issued	2015
dc.identifier	10.1016/j.eswa.2015.06.030
dc.identifier.citation	42, 21, 8086-8094
dc.identifier.issn	09574174
dc.identifier.uri	https://hdl.handle.net/20.500.12728/3590
dc.description	Abstract The reliability and increasing performance of search-tree-based interval solvers for solving numerical systems of constraints make them applicable to various expert system domains. Filtering methods are applied in each node of the search tree to reduce the variable domains without the loss of solutions. Current interval-based solvers generally leave it up to the solver designer to decide which set of filtering methods to apply to solve a particular problem. In this work, we propose an adaptive strategy to dynamically determine the set of filtering methods that will be applied in each node of the search tree. Our goal is twofold: first, we want to simplify the task of the solver designer, and second, we believe that an adaptive strategy may improve the average performance of the current state-of-the-art strategies. The proposed adaptive mechanism attempts to avoid calling costly filtering methods when their probability of filtering domains is low. We assume that fruitful filtering occurs in nearby revisions or clusters. Thus, the decision about whether or not to apply a filtering method is based on a cluster detection mechanism. When a cluster is detected, the associated methods are consecutively applied in order to exploit the cluster. Alternately, in zones without clusters, only a cheap method is applied, thus reducing the filtering effort in large portions of the search. We compare our approach with state-of-the-art strategies, demonstrating its effectiveness. © 2015 Elsevier Ltd.
dc.language.iso	en
dc.publisher	Elsevier Ltd
dc.subject	Branch and bound
dc.subject	Consistency techniques
dc.subject	Filtering algorithms
dc.subject	Interval-based solvers
dc.subject	Branch and bound method
dc.subject	Constraint satisfaction problems
dc.subject	Expert systems
dc.subject	Adaptive mechanism
dc.subject	Adaptive strategy
dc.subject	Cluster detection
dc.subject	Consistency techniques
dc.subject	Filtering algorithm
dc.subject	Interval-based solvers
dc.subject	Numerical constraint satisfaction problems
dc.subject	Numerical systems
dc.subject	Filtration
dc.title	Adaptive filtering strategy for numerical constraint satisfaction problems
dc.type	Article