A Connectionist Approach for Solving Large Constraint Satisfaction Problems

An efficient neural network technique is presented for the solution of binary constraint satisfaction problems. The method is based on the application of a double-update technique to the operation of the discrete Hopfield--type neural network that can be constructed for the solution of such problems. This operation scheme ensures that the network moves only between consistent states, such that each problem variable is assigned exactly one value, and leads to a fast and efficient search of the problem state space. Extensions of the proposed method are considered in order to include several optimisation criteria in the search. Experimental results concerning many real-size instances of the Radio Links Frequency Assignment Problem demonstrate very good performance. 1 Introduction Constraint satisfaction problems (CSPs) [1] represent typical combinatorial problems that are usually solved with search techniques based on backtracking algorithms [2, 3]. In general, these techniques work well..