An information-based neural approach to constraint satisfaction

Research output: Contribution to journalArticle

Standard

An information-based neural approach to constraint satisfaction. / Jönsson, Henrik; Söderberg, Bo.

In: Neural Computation, Vol. 13, No. 8, 08.2001, p. 1827-1838.

Research output: Contribution to journalArticle

Harvard

APA

CBE

MLA

Vancouver

Author

RIS

TY - JOUR

T1 - An information-based neural approach to constraint satisfaction

AU - Jönsson, Henrik

AU - Söderberg, Bo

PY - 2001/8

Y1 - 2001/8

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0035434198&partnerID=8YFLogxK

U2 - 10.1162/08997660152469369

DO - 10.1162/08997660152469369

M3 - Article

AN - SCOPUS:0035434198

VL - 13

SP - 1827

EP - 1838

JO - Neural Computation

JF - Neural Computation

SN - 1530-888X

IS - 8

ER -