Extending EGENET with lazy constraint consistency

Peter Stuckey, Vincent Tam

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

2 Citations (Scopus)

Abstract

Constraint satisfaction problems (CSPs) occur widely in real-life applications such as bin-packing, planning and scheduling. EGENET, a neural network simulator based on the min-conflict heuristic, has had remarkable success in solving hard CSPs such as hard graph-colouring problems. Consistency techniques such as arc consistency have been extensively used to improve the search behaviour of complete search methods, by removing values and combinations of values that cannot take part in any solution. They are not typically used for stochastic search methods such as EGENET. In this paper we show how to efficiently incorporate consistency methods in EGENET. This improves the convergence behaviour of EGENET and also makes it able to detect insoluble CSPs. We compare the improved EGENET against the original version and versions incorporating state-of-art consistency techniques such as AC-4 or PC-4.

Original languageEnglish
Title of host publicationProceedings of the International Conference on Tools with Artificial Intelligence
Pages248-257
Number of pages10
Publication statusPublished - 1 Dec 1997
Externally publishedYes
EventProceedings if the 1997 IEEE 9th IEEE International Conference on Tools with Artificial Intelligence - Newport Beach, CA, USA
Duration: 3 Nov 19978 Nov 1997

Conference

ConferenceProceedings if the 1997 IEEE 9th IEEE International Conference on Tools with Artificial Intelligence
CityNewport Beach, CA, USA
Period3/11/978/11/97

Cite this