A New Adaptive Parameterized Consistency Algorithm

DOI

10.2991/lemcs-15.2015.204How to use a DOI?

Keywords

Constraint satisfaction problem; Constraint propagation; Adaptive; Backtracking; Parameterized consistency

Abstract

Nowadays all kinds of constraint solver support the same level of local consistency on all problems. The authors proposed a new adaptive parameterized consistency algorithm which adjusted the level of consistency depending on the depth of their supports in there domain. To this end, the authors gave the notion of the improved distance to the end of a value, which is the dynamic distance, and it reflected the current state of the assignment. If the size of the variable domain reached its given threshold or the ratio to the original size reached its given threshold, the constraint solving process used the stronger consistency technique to propagate the assigned value. The faster deletion of invalid value, the easier cause backtracking. It is more likely to find the problem as soon as possible. Finally the authors carry on the experiments on some benchmark instances, the results showed that the new algorithm can outperform original parameterized consistency algorithm on many problems and is a promising method.

Copyright

© 2015, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Yunpeng Wu
AU  - Yonggang Zhang
AU  - Sibo Zhang
PY  - 2015/07
DA  - 2015/07
TI  - A New Adaptive Parameterized Consistency Algorithm
BT  - Proceedings of the International Conference on Logistics, Engineering, Management and Computer Science
PB  - Atlantis Press
SP  - 1032
EP  - 1036
SN  - 1951-6851
UR  - https://doi.org/10.2991/lemcs-15.2015.204
DO  - 10.2991/lemcs-15.2015.204
ID  - Wu2015/07
ER  -