Extending GENET with lazy arc consistency

Peter J. Stuckey, Vincent Tam

Research output: Contribution to journalArticleResearchpeer-review

5 Citations (Scopus)

Abstract

Many important applications, such as graph coloring, scheduling and production planning, can be solved by GENET, a local search method which is used to solve binary constraint satisfaction problems (CSP's). Where complete search methods are typically augmented with consistency methods to reduce the search, local search methods are not. We propose a consistency technique, lazy arc consistency, which is suitable for use within GENET. We show it can improve the efficiency of the GENET search on some instances of binary CSP's, and does not suffer the overhead of full arc consistency.

Original languageEnglish
Pages (from-to)698-703
Number of pages6
JournalIEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans
Volume28
Issue number5
DOIs
Publication statusPublished - 1 Dec 1998
Externally publishedYes

Keywords

  • Arc consistency
  • Constraint satisfaction

Cite this