Title
Adaptive filtering strategy for numerical constraint satisfaction problems
Date Issued
15 July 2015
Access level
metadata only access
Resource Type
journal article
Author(s)
Publisher(s)
Elsevier Ltd
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.
Start page
8086
End page
8094
Volume
42
Issue
21
Language
English
OCDE Knowledge area
Sistemas de automatización, Sistemas de control
Subjects
Scopus EID
2-s2.0-84937605727
Source
Expert Systems with Applications
ISSN of the container
09574174
Source funding
Sponsor(s)
Ignacio Araya is supported by the Fondecyt Project 11121366, Ricardo Soto is supported by the Fondecyt Project 11130459, Broderick Crawford is supported by the Fondecyt Project 1140897.
Sources of information:
Directorio de Producción Científica
Scopus