An information-based neural approach to constraint satisfaction

Research output: Contribution to journalArticle

Abstract

A novel artificial neural network approach to constraint satisfaction problems is presented. Based on information-theoretical considerations, it differs from a conventional mean-field approach in the form of the resulting free energy. The method, implemented as an annealing algorithm, is numerically explored on a testbed of K-SAT problems. The performance shows a dramatic improvement over that of a conventional mean-field approach and is comparable to that of a state-of-the-art dedicated heuristic (GSAT+walk). The real strength of the method, however, lies in its generality. With minor modifications, it is applicable to arbitrary types of discrete constraint satisfaction problems.

Details

Authors
Organisations
Original languageEnglish
Pages (from-to)1827-1838
Number of pages12
JournalNeural Computation
Volume13
Issue number8
Publication statusPublished - 2001 Aug
Publication categoryResearch
Peer-reviewedYes