Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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
and
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
2016-04-01 11:48:35
date last changed
2024-02-23 08:41:51
@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}},
  keywords     = {{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}},
  doi          = {{10.1016/S0004-3702(02)00291-6}},
  volume       = {{142}},
  year         = {{2002}},
}