Centro Investigación en Educación Superior

Adaptive filtering strategy for numerical constraint satisfaction problems

CATEGORÍA(S): , , , .
AUTOR(ES): Ignacio Araya / Ricardo Soto / Broderick Crawford.
Licencia Creative Commons Reconocimiento CC BY. Esta obra está bajo una Licencia Creative Commons Reconocimiento CC BY 4.0 Internacional.

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.

Documentos relacionados

Portada 1

Serie Creación – Documento de trabajo n°29: Apunte de clase elaborado por Docente – Kinesiólogo. Juan Inostroza Silva Universidad San Sebastián de Puerto Montt.

La Terapia de Onda Corta Pulsada (TOCP) es una modalidad ampliamente utilizado en el Reino Unido (Al Mandil y Watson […]

Saltar a la barra de herramientas