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.
Complete list of metadatas

Cited literature [10 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00839025
Contributor : Joël Quinqueton <>
Submitted on : Tuesday, January 23, 2018 - 3:53:11 PM
Last modification on : Thursday, May 24, 2018 - 3:59:23 PM
Long-term archiving on: Thursday, May 24, 2018 - 2:48:42 PM

File

cp13-p-maxrpc.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Amine Balafrej, Christian Bessière, 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⟩

Share

Metrics

Record views

273

Files downloads

281