SOLVING INEQUALITY CONSTRAINED COMBINATORIAL OPTIMIZATION PROBLEMS BY THE HOPFIELD NEURAL NETWORKS

The Hopfield neural networks are extended to handle inequality constraints where linear combinations of variables are lower- or upper-bounded. Then by eigenvalue analysis, the effects of the inequality constraints are analyzed and the following results are obtained: (a) if a combinatorial solution obtained by the networks satisfies the inequality constraints, the eigenvalues corresponding to the solution are the same as those without the inequality constraints; and (b) a combinatorial solution which satisfies the inequality constraints is stable if the energy, without the inequality constraints, of the solution is the smallest among those of the adjacent combinatorial solutions. From these results, the weights in the energy function are determined so that a combinatorial solution which satisfies the equality constraints, but does not satisfy the inequality constraints, is unstable. The results are verified for the knapsack problem and the transportation problem. For the latter problem, convergence to the optimal solution is improved by the introduction of the inequality constraints.