Proceedings of the International Conference on Logistics, Engineering, Management and Computer Science

A New Adaptive Parameterized Consistency Algorithm

Authors
Yunpeng Wu, Yonggang Zhang, Sibo Zhang
Corresponding Author
Yunpeng Wu
Available Online July 2015.
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)

Volume Title
Proceedings of the International Conference on Logistics, Engineering, Management and Computer Science
Series
Advances in Intelligent Systems Research
Publication Date
July 2015
ISBN
978-94-6252-102-5
ISSN
1951-6851
DOI
10.2991/lemcs-15.2015.204How to use a DOI?
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/).

Cite this article

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  -