Henrik Jönsson and Bo Söderberg
An Information-Based Neural Approach to Generic Constraint Satisfaction
To appear in Artificial Intelligence 142:1, 1--17 (2002)

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.

LU TP 00-40