An information-based neural approach to generic constraint satisfaction
(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:
https://lup.lub.lu.se/record/324609
- author
- Jönsson, Henrik LU and Söderberg, Bo LU
- organization
- publishing date
- 2002
- 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}}, }