Extending GENET with lazy arc consistency

Author

Stuckey, Peter J. ; Tam, Vincent

Author_Institution

Dept. of Comput. Sci., Melbourne Univ., Parkville, Vic., Australia

Volume

28

Issue

5

fYear

1998

fDate

9/1/1998 12:00:00 AM

Firstpage

698

Lastpage

703

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 (CSPs). 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 CSPs, and does not suffer the overhead of full arc consistency

Keywords

computational complexity; constraint theory; graph colouring; logic programming; neural nets; search problems; GENET local search method; binary constraint satisfaction problems; consistency technique; graph coloring; lazy arc consistency; production planning; scheduling; Algorithm design and analysis; Artificial neural networks; Convergence; Evolutionary computation; Job shop scheduling; Logic programming; Microprogramming; Production planning; Search methods; Simulated annealing;

fLanguage

English

Journal_Title

Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on

Publisher

ieee

ISSN

1083-4427

Type

jour

DOI

10.1109/3468.709620

Filename

709620