Skip to Main content Skip to Navigation
Conference papers

Lazy arc consistency

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

https://hal.inrae.fr/hal-02771457
Contributor : Migration Prodinra Connect in order to contact the contributor
Submitted on : Thursday, June 4, 2020 - 12:20:09 PM
Last modification on : Thursday, July 16, 2020 - 11:58:02 AM

Identifiers

  • HAL Id : hal-02771457, version 1
  • PRODINRA : 136085

Collections

Citation

Thomas Schiex, J.C. Régin, Christine Gaspin, G. Verfaillie. Lazy arc consistency. National American Conference on Artificial Intelligent, 1996, Portland, United States. ⟨hal-02771457⟩

Share

Metrics

Record views

9