An information-based neural approach to generic constraint satisfaction.

DOI10.1016/S0004-3702(02)00291-6MaRDI QIDQ1852859zbMATH OpenOpenAlexFDO

Authors Henrik Jönsson, Bo Söderberg

Publication date 21 January 2003

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0004-3702(02)00291-6

zbMATH Keywords

Artificial neural networkConnectionistConstraint satisfactionGraph coloringHeuristicInformationMean-field annealing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Learning and adaptive systems in artificial intelligence (68T05) Approximation methods and heuristics in mathematical programming (90C59)

Review text

A novel artificial neural network heuristic 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.

Recommendations

• An information-based neural approach to constraint satisfaction
• Connectionist networks for constraint satisfaction
• Using artificial neural networks for constraint satisfaction problem
• Solving Constraint-Satisfaction Problems with Distributed Neocortical-Like Neuronal Networks
• An artificial neural network satisfiability tester

Cites work

• ``Neural computation of decisions in optimization problems
• An information-based neural approach to constraint satisfaction
• Determining computational complexity from characteristic ``phase transitions
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 487935 (Why is no real title available?)
• scientific article; zbMATH DE number 1105634 (Why is no real title available?)
• scientific article; zbMATH DE number 956851 (Why is no real title available?)
• New methods to color the vertices of a graph
• Optimization by simulated annealing
• Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
• Phase transitions and the search problem
• Some experiments with simulated annealing for coloring graphs
• Statistical field theory. With a foreword by David Pines

Cited in

(2)

• An information-based neural approach to constraint satisfaction
• Using artificial neural networks for constraint satisfaction problem

Describes a project that uses

Uses Software

• DIMACS

This page was built for publication: An information-based neural approach to generic constraint satisfaction.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1852859)