Advanced

An information-based neural approach to generic constraint satisfaction

Jönsson, Henrik LU and Söderberg, Bo LU (2002) In Artificial Intelligence 142(1). p.1-17
Abstract
A novel artificial neural network heuristic (INN) for general constraint satisfaction problems is presented. extending a recently suggested method restricted to boolean variables. In contrast to conventional ANN methods, it employs a particular type of non-polynomial cost function, based on the information balance between variables and constraints in a mean-field setting. Implemented as an annealing algorithm, the method is numerically explored on a testbed of Graph Coloring problems. The performance is comparable to that of dedicated heuristics, and clearly superior to that of conventional mean-field annealing.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
constraint satisfaction, connectionist, artificial, neural network, heuristic information, mean-field annealing, graph coloring
in
Artificial Intelligence
volume
142
issue
1
pages
1 - 17
publisher
Elsevier
external identifiers
  • wos:000179018300001
  • scopus:0036837931
ISSN
1872-7921
DOI
10.1016/S0004-3702(02)00291-6
language
English
LU publication?
yes
id
4e8f3f3e-0ef0-4ac8-9fca-8112c06cf3ff (old id 324609)
date added to LUP
2007-10-31 13:38:06
date last changed
2017-01-01 04:33:53
@article{4e8f3f3e-0ef0-4ac8-9fca-8112c06cf3ff,
  abstract     = {A novel artificial neural network heuristic (INN) for general constraint satisfaction problems is presented. extending a recently suggested method restricted to boolean variables. In contrast to conventional ANN methods, it employs a particular type of non-polynomial cost function, based on the information balance between variables and constraints in a mean-field setting. Implemented as an annealing algorithm, the method is numerically explored on a testbed of Graph Coloring problems. The performance is comparable to that of dedicated heuristics, and clearly superior to that of conventional mean-field annealing.},
  author       = {Jönsson, Henrik and Söderberg, Bo},
  issn         = {1872-7921},
  keyword      = {constraint satisfaction,connectionist,artificial,neural network,heuristic information,mean-field annealing,graph coloring},
  language     = {eng},
  number       = {1},
  pages        = {1--17},
  publisher    = {Elsevier},
  series       = {Artificial Intelligence},
  title        = {An information-based neural approach to generic constraint satisfaction},
  url          = {http://dx.doi.org/10.1016/S0004-3702(02)00291-6},
  volume       = {142},
  year         = {2002},
}