Title :
2-C6: An fine-grained algorithm to achieve 2-consistency
Author :
Arangu, Marlene ; Salido, M.A.
Author_Institution :
Dipt. de Tec. Cuantitativas, Univ. Centroccidental Lisandro Alvarado, Valencia, Spain
Abstract :
Most arc-consistency algorithms take for granted that CSPs are binary (all constraints involve two variables) and normalized (two different constraints do not involve exactly the same variables). When these algorithms perform pruning of values, propagation mechanisms are activated at both levels: value (fine-grained), and constraint (coarse-grained). Thus, values that might become inconsistent because of the pruning are re-checked to ensure their consistency. In this paper, we relax the assumption that the constraints are normalized and we work on problems with non-normalized constraints (there may be more than one constraint that involves the same two variables). In this type of problems, arc consistency techniques are not able to perform the same amount of pruning as 2-consistency techniques, unless a normalization process is performed previously. In this paper we propose the Algorithm 2-C6, which is a reformulation of AC6. The algorithm 2-C6 achieves 2-consistency and performs the finegrained propagations. In empirical evaluations, we compare the performance of the proposed algorithm 2-C6 with the following arc-consistency algorithms: AC3, AC6 and AC7 (coarse-grained and fine-grained, respectively) and with 2-C3, which is a 2-consistency coarse-grained algorithm. From these evaluations, we conclude that the 2-consistency techniques are more appropriated for this type of problem.
Keywords :
algorithm theory; constraint handling; 2-C3 coarse-grained algorithm; 2-C6 fine-grained algorithm; AC3 arc-consistency algorithm; AC6 arc-consistency algorithm; AC7 arc-consistency algorithm; CSP; arc-consistency algorithms; coarse-grained algorithm; constraint satisfaction problems; empirical evaluations; non-normalized constraints; propagation mechanisms; Benchmark testing; Conferences; Electronic mail; Filtering; Random access memory; Silicon; Silicon compounds; Consistency Techniques; Constraint Satisfaction Problems; Filtering Techniques;
Conference_Titel :
Computing Conference (CLEI), 2013 XXXIX Latin American
Conference_Location :
Naiguata
Print_ISBN :
978-1-4799-2957-3
DOI :
10.1109/CLEI.2013.6670595