As a guest user you are not logged in or recognized by your IP address. You have
access to the Front Matter, Abstracts, Author Index, Subject Index and the full
text of Open Access publications.
Arc-consistency algorithms are widely used to prune the search space of Constraint Satisfaction Problems (CSPs). One of the most well-known arc-consistency algorithms for filtering CSPs is AC3. This algorithm repeatedly carries out revisions and requires support checks for identifying and deleting all unsupported values from the domains. Nevertheless, many revisions are ineffective, that is, they cannot delete any value and they require a lot of checks and are time-consuming. We present AC3-OP, an optimized and reformulated version of AC3 that reduces the number of constraint checks and prunes the same CSP search space with arithmetic constraints. In inequality constraints, AC3-OP, checks the binary constraints in both directions (full arc-consistency), but it only propagates new constraints in one direction. Thus, it avoids checking redundant constraints that do not filter any value of the variable's domain. The evaluation section shows the improvement of AC3-OP over AC3 in random instances.
This website uses cookies
We use cookies to provide you with the best possible experience. They also allow us to analyze user behavior in order to constantly improve the website for you. Info about the privacy policy of IOS Press.
This website uses cookies
We use cookies to provide you with the best possible experience. They also allow us to analyze user behavior in order to constantly improve the website for you. Info about the privacy policy of IOS Press.