Adaptive Parameterized Consistency - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2013

Adaptive Parameterized Consistency

Abstract

State-of-the-art constraint solvers uniformly maintain the same level of local consistency (usually arc consistency) on all the instances. We propose parameterized local consistency, an original approach to adjust the level of consistency depending on the instance and on which part of the instance we propagate. We do not use as parameter one of the features of the instance, as done for instance in portfolios of solvers. We use as parameter the stability of values, which is a feature based on the state of the arc consistency algorithm during its execution. Parameterized local consistencies choose to enforce arc consistency or a higher level of local consistency on a value depending on whether the stability of the value is above or below a given threshold. We also propose a way to dynamically adapt the parameter, and thus the level of local consistency, during search. This approach allows us to get a good trade-off between the number of values pruned and the computational cost. We validate our approach on various problems from the CSP competition.
Fichier principal
Vignette du fichier
cp13-p-maxrpc.pdf (374.95 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-00839025 , version 1 (23-01-2018)

Identifiers

Cite

Amine Balafrej, Christian Bessiere, Remi Coletta, El Houssine Bouyakhf. Adaptive Parameterized Consistency. CP: Principles and Practice of Constraint Programming, Sep 2013, Uppsala, Sweden. pp.143-158, ⟨10.1007/978-3-642-40627-0_14⟩. ⟨lirmm-00839025⟩
176 View
189 Download

Altmetric

Share

More