Premium
The dilemma between arc and bounds consistency
Author(s) -
Pothitos Nikolaos,
Stamatopoulos Panagiotis
Publication year - 2020
Publication title -
international journal of intelligent systems
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.291
H-Index - 87
eISSN - 1098-111X
pISSN - 0884-8173
DOI - 10.1002/int.22259
Subject(s) - local consistency , constraint satisfaction problem , consistency (knowledge bases) , weak consistency , computer science , constraint satisfaction , consistency model , sequential consistency , strong consistency , constraint (computer aided design) , mathematical optimization , mathematics , algorithm , theoretical computer science , statistics , artificial intelligence , geometry , estimator , probabilistic logic , correctness
Consistency enforcement is used to prune the search tree of a constraint satisfaction problem (CSP). Arc consistency (AC) is a well‐studied consistency level, with many implementations. Bounds consistency (BC), a looser consistency level, is known to have equal time complexity to AC. To solve a CSP, we have to implement an algorithm of our own or employ an existing solver. In any case, at some point, we have to decide between enforcing either AC or BC. As the choice between AC or BC is more or less predefined and currently made without considering the individualities of each CSP, this study attempts to make this decision deterministic and efficient, without the need of trial and error. We find that BC fits better while solving a CSP with its maximum domains' size being greater than its constrained variables number. We study the behavior of maintaining arc or bounds consistency during search, and we show how the overall search methods complexity is affected by the employed consistency level.