Adaptive filtering strategy for numerical constraint satisfaction problems

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

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.

Original languageEnglish
Article number10107
Pages (from-to)8086-8094
Number of pages9
JournalExpert Systems with Applications
Volume42
Issue number21
DOIs
StatePublished - 15 Jul 2015
Externally publishedYes

Keywords

  • Branch and bound
  • Consistency techniques
  • Filtering algorithms
  • Interval-based solvers

Fingerprint

Dive into the research topics of 'Adaptive filtering strategy for numerical constraint satisfaction problems'. Together they form a unique fingerprint.

Cite this