M. Nagamatu and T. Nakano (Japan)
constraint satisfaction, Lagrangian method, neural network, local minima.
The CSP (Constraint Satisfaction Problem) is to find a value assignment to all variables which satisfies all given constraints. CSP can express many problems in many field of computer science, and is a theoretically and practically important problem. For solution search problems like the CSP, local search techniques are well used. However the most serious drawback of the local search is being trapped by local minima. We proposed a neural network dynamics called LPPH (Lagrange Programming neural network with Polarized High-order connection) for solving the SAT (SATisfiability problem of propositional calculus). The LPPH has the following properties: 1) it does not stop at any point which is not the solution, and 2) when it comes near to some solution, it converges to the solution. From these properties, the LPPH can moves around in the state space being not trapped by any point except solutions, and finds a solution eventually. The experiments proved its efficiency. In this paper we extend the LPPH for solving the CSP. We can construct a straightforward extension of the LPPH. However it is quite inefficient. By introducing operators which find the nth largest or nth smallest element, we can propose a very efficient extension called LPPH-CSP. We investigate the performance by experiments and compare it with already proposed methods.
Important Links:
Go Back
