NEURAL NETWORKS FOR FINITE CONSTRAINT SATISFACTION

Constraint Satisfaction Problems (CSPs) are in general NP-hard, and a general deterministic polynomial time algorithm is not known. They pla y a central role in real-life problems. The satisfaction of a Conjunct ive Normal Form (CNF-SAT) is the core of any CSP. We present a new mod elisation technique for any CSP with finite variable domains, and, in particular, for solving CNF-SAT. The knowledge representation is based on two fundamental types of constraint: the choice constraint, and th e exclusion constraint. These models are then implemented by means of several different neural networks, some based on backpropagation learn ing and others on different procedures. All these networks are trained through a supervised procedure, and learn to efficiently solve CNF-SA T. The results of significant tests ave described: they show that some networks can effectively solve the proposed problems.