An Information-Based Neural Approach to Constraint Satisfaction
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.
Cite
Text
Jönsson and Söderberg. "An Information-Based Neural Approach to Constraint Satisfaction." Neural Computation, 2001. doi:10.1162/08997660152469369Markdown
[Jönsson and Söderberg. "An Information-Based Neural Approach to Constraint Satisfaction." Neural Computation, 2001.](https://mlanthology.org/neco/2001/jonsson2001neco-informationbased/) doi:10.1162/08997660152469369BibTeX
@article{jonsson2001neco-informationbased,
title = {{An Information-Based Neural Approach to Constraint Satisfaction}},
author = {Jönsson, Henrik and Söderberg, Bo},
journal = {Neural Computation},
year = {2001},
pages = {1827-1838},
doi = {10.1162/08997660152469369},
volume = {13},
url = {https://mlanthology.org/neco/2001/jonsson2001neco-informationbased/}
}