<abstract xml:lang="en" xmlns="http://www.w3.org/1999/xhtml"><p>Constraint programming is a powerful software technology for solving numerous real-life problems. Many of these problems can be modeled as Constraint Satisfaction Problems (CSPs) and solved using constraint programming techniques. However, solving a CSP is NP-complete so filtering techniques to reduce the search space are still necessary. Arc-consistency algorithms are widely used to prune the search space. The concept of arc-consistency is bidirectional, i.e., it must be ensured in both directions of the constraint (direct and inverse constraints). Two of the most well-known and frequently used arc-consistency algorithms for filtering CSPs are AC3 and AC4. These algorithms repeatedly carry out revisions and require support checks for identifying and deleting all unsupported values from the domains. Nevertheless, many revisions are ineffective, i.e., they cannot delete any value and consume a lot of checks and time. In this paper, we present AC4-OP, an optimized version of AC4 that manages the binary and non-normalized constraints in only one direction, storing the inverse founded supports for their later evaluation. Thus, it reduces the propagation phase avoiding unnecessary or ineffective checking. The use of AC4-OP reduces the number of constraint checks by 50% while pruning the same search space as AC4. The evaluation section shows the improvement of AC4-OP over AC4, AC6 and AC7 in random and non-normalized instances.</p></abstract>

Constraint programming is a powerful software technology for solving numerous real-life problems. Many of these problems can be modeled as Constraint Satisfaction Problems (CSPs) and solved using constraint programming techniques. However, solving a CSP is NP-complete so filtering techniques to reduce the search space are still necessary. Arc-consistency algorithms are widely used to prune the search space. The concept of arc-consistency is bidirectional, i.e., it must be ensured in both directions of the constraint (direct and inverse constraints). Two of the most well-known and frequently used arc-consistency algorithms for filtering CSPs are AC3 and AC4. These algorithms repeatedly carry out revisions and require support checks for identifying and deleting all unsupported values from the domains. Nevertheless, many revisions are ineffective, i.e., they cannot delete any value and consume a lot of checks and time. In this paper, we present AC4-OP, an optimized version of AC4 that manages the binary and non-normalized constraints in only one direction, storing the inverse founded supports for their later evaluation. Thus, it reduces the propagation phase avoiding unnecessary or ineffective checking. The use of AC4-OP reduces the number of constraint checks by 50% while pruning the same search space as AC4. The evaluation section shows the improvement of AC4-OP over AC4, AC6 and AC7 in random and non-normalized instances.

A fine-grained arc-consistency algorithm for non-normalized constraint satisfaction problems

Institute of Industrial Informatics and Automatics, Technical University of Valencia, Camino de Vera, s/n. 46020 Valencia, Spain

International Journal of Applied Mathematics and Computer Science

Constraint programming is a powerful software technology for solving numerous real-life problems. Many of these problems can be modeled as Constraint...

A fine-grained arc-consistency algorithm for non-normalized constraint satisfaction problems

Publié en ligne: 21 déc. 2011

Pages: 733 - 744

DOI: https://doi.org/10.2478/v10006-011-0058-2

Mots clés
constraint satisfaction problems, filtering techniques, consistency algorithms

This content is open access.

A fine-grained arc-consistency algorithm for non-normalized constraint satisfaction problems

Publié en ligne: 21 déc. 2011

Pages: 733 - 744

DOI: https://doi.org/10.2478/v10006-011-0058-2

Mots clésconstraint satisfaction problems, filtering techniques, consistency algorithms

This content is open access.

Mots clés
constraint satisfaction problems, filtering techniques, consistency algorithms