Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

An information-based neural approach to constraint satisfaction

Jönsson, Henrik LU and Söderberg, Bo LU (2001) In Neural Computation 13(8). p.1827-1838
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.

Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Contribution to journal
publication status
published
in
Neural Computation
volume
13
issue
8
pages
12 pages
publisher
MIT Press
external identifiers
  • scopus:0035434198
ISSN
0899-7667
DOI
10.1162/08997660152469369
language
English
LU publication?
yes
id
a6809e4a-0f9a-4fc4-9331-d056dbb65e96
date added to LUP
2016-10-03 19:09:03
date last changed
2022-12-14 02:58:11
@article{a6809e4a-0f9a-4fc4-9331-d056dbb65e96,
  abstract     = {{<p>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.</p>}},
  author       = {{Jönsson, Henrik and Söderberg, Bo}},
  issn         = {{0899-7667}},
  language     = {{eng}},
  number       = {{8}},
  pages        = {{1827--1838}},
  publisher    = {{MIT Press}},
  series       = {{Neural Computation}},
  title        = {{An information-based neural approach to constraint satisfaction}},
  url          = {{http://dx.doi.org/10.1162/08997660152469369}},
  doi          = {{10.1162/08997660152469369}},
  volume       = {{13}},
  year         = {{2001}},
}