Proceedings of the 2017 2nd International Conference on Control, Automation and Artificial Intelligence (CAAI 2017)

<Previous Article In Volume
Next Article In Volume>

lmaxRPCls: An Algorithm Utilizing Light Symmetry for Approximating maxRPC in Constraint Programming

Authors
Zhiying Xu, Shihui Song, Zhanshan Li
Corresponding Author
Zhiying Xu
Available Online June 2017.
DOI
10.2991/caai-17.2017.87How to use a DOI?
Keywords
constraint programming; symmetry; maxRPC
Abstract

Constraint satisfaction problem (CSP) can be widely applied in many areas. This paper investigates the maximum restricted path consistency algorithm. There is a large quantity of useless checks in the process of searching for a PC-support with the most popular algorithm lmaxRPC3rm. Since lmaxRPC3rm has to examine the whole domain of a variable to ascertain whether a PC-support exists. The efficiency of the search can be improved by eliminating such useless checks. Firstly, this paper analyses the features which accounts for the existence of these ineffective checks. And then, this paper discusses some methods of solving these problems. Afterwards, a new data structure is put forward to strengthen residual supports and weaken the use of multidirectionality to narrow the range of search. A new algorithm, lmaxRPCls, which exploits the results above is proposed and it is proved that lmaxRPCls is correct and complete. It is also proved that the time complexity of this new algorithm is better than that of lmaxRPC3rm. Experimental results show that lmaxRPCls performs better in most benchmark instances and it can improve the performance by 65% in the best case.

Copyright
© 2017, 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)

<Previous Article In Volume
Next Article In Volume>
Volume Title
Proceedings of the 2017 2nd International Conference on Control, Automation and Artificial Intelligence (CAAI 2017)
Series
Advances in Intelligent Systems Research
Publication Date
June 2017
ISBN
10.2991/caai-17.2017.87
ISSN
1951-6851
DOI
10.2991/caai-17.2017.87How to use a DOI?
Copyright
© 2017, 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

risenwbib
TY  - CONF
AU  - Zhiying Xu
AU  - Shihui Song
AU  - Zhanshan Li
PY  - 2017/06
DA  - 2017/06
TI  - lmaxRPCls: An Algorithm Utilizing Light Symmetry for Approximating maxRPC in Constraint Programming
BT  - Proceedings of the 2017 2nd International Conference on Control, Automation and Artificial Intelligence (CAAI 2017)
PB  - Atlantis Press
SP  - 382
EP  - 385
SN  - 1951-6851
UR  - https://doi.org/10.2991/caai-17.2017.87
DO  - 10.2991/caai-17.2017.87
ID  - Xu2017/06
ER  -