An information-based neural approach to constraint satisfaction

A novel artificial neural network approach to constraint satisfaction probl ems is presented. Based on information-theoretical considerations, it diffe rs from a conventional mean-field approach in the form of the resulting fre e 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 comparab le 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 modific ations, it is applicable to arbitrary types of discrete constraint satisfac tion problems.