Syracuse

Lazy arc consistency

Archive ouverte

Schiex, Thomas | Régin, J.C. | Gaspin, Christine | Verfaillie, G.

Edité par CCSD -

* INRA - Unité de Biométrie, Centre de Toulouse (FRA) Diffusion du document : INRA - Unité de Biométrie, Centre de Toulouse (FRA). International audience. Arc consistency filtering is widely used in the framework of binary constraint satisfaction problems : with a low complexity, inconsistencymay be detected and domains are filtered. In this paper, we show that when detecting inconsistency is the objective, a systematic domain filtering is useless and a lazy approach is more adequate. Whereas usual arc consistency algorithms produce the maximum arc consistent sub-domain, when it exists, we propose a method, called LAC_7, which only looks for any arc consistent sub-domain. The algorithm is then extended to provide the additional service of locating one variable with a minimum domain cardinality in the maximum arc consistent sub-domain, without necessarily computing all domain sizes. Finally, we compare traditional AC enforcing and lazy AC enforcing using several benchmark problems, both randomly generated CSP and real life problems.

• Description
• Sujet/Public
• Outil
• Outil d'anticipation
• Mémoire et thèse
• Gestion