Solving inequality constrained combinatorial optimization problems by the hopfield neural networks

✍ Scribed by Shigeo Abe; Junzo Kawakami; Kotaroo Hirasawa

• Publisher: Elsevier Science
• Year: 1992
• Tongue: English
• Weight: 543 KB
• Volume: 5
• Category: Article
• ISSN: 0893-6080
• DOI: 10.1016/s0893-6080(05)80043-7

✦ Synopsis

The Hop.fteld neural networks are ~:~tended to handle inequality constraints where linear combinations of variables are lower-or upper-bounded. Then b)' eigenvahw analysis, the effects q/'the inequality constraints are analyzed and the lbllowing results are obtained" (a) f a combinatorial solution obtained by the networks sati~lk's the inequalit), constraints, the eigenvahws 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 f the energ); without the inequality constraints, of the sohttion is the smallest among those o['the adjacent combinatorial solutions. From these results, the n'eights in the energy /hnction are determined so that a combinatorial solution which satis.fies the equality constraints, but does not sati.~/.i' the inequality constraints, is unstable. The resuhs are vero~ed fi;r 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.