Encoding logical constraints into neural network cost functions

The authors introduce the use of logical consequences in determining cost functions for neural networks which solve optimization or constraint-satisfaction problems. This technique estimates the changes required in the remaining neuron outputs in order to maintain a valid solution when a selected neuron is forced on or off. From this estimate, an estimate can be made of the cost change due to the change in the selected neuron. The set of estimated costs for all the neurons is then used to update their respective outputs. Applying logical consequences in some problems eliminates the need to use penalty functions to transform constrained problems into unconstrained problems suitable for solution by neural nets. The neural nets derived with this technique nearly always produced valid solutions to the traveling salesman problem, and the solutions were only 5% above the best solutions found using simulated annealing. Graph bipartitioning was also performed, but the percentage of balanced solutions fell into the 70% to 90% range due to a violation of one of the implicit assumptions in the model