General solution for combinatorial problems by neural networks

Yao et al. have proposed the Dynamic-Static Neural network (DS-net) which includes the Tank and Hopfield model for linear programming problems as its special case. This paper proposes a modified DS-net which is capable of solving optimization problems with quadratic constraints. Because the 3-satisfiability problem of Boolean formula can be transformed to problems of this type, the model is applied to the problem. The simulation experiments using a digital computer show that this formulation bring the merit of greedy methods to the neural network solution and the initial state satisfying constraints is excellent for obtaining the optimal solution.