Summary
International Symposium on Nonlinear Theory and its Applications
2009
Session Number:B4L-D
Session:
Number:B4L-D2
The Quartic Form Energy Function for General Combinatorial Optimization Problems
Takahiro Sota, Yoshihiro Hayakawa, Koji Nakajima,
pp.-
Publication Date:2009/10/18
Online ISSN:2188-5079
Summary:
The Inverse function Delayed model (ID model) is a neuron model that has negative resistance dynamics. The negative resistance can destabilize local minimum states, which are undesirable network responses, so that the ID network can remove these states. Actually, we have demonstrated that the ID network can perfectly remove all local minima with N-Queen problems or 4-Color problems, where stationary states are only correct answer. Moreover, we have also applied the same method to the case of Traveling Salesman Problems (TSP) by expanding the energy function to the quartic form that means higher order synaptic connections. However, we need general energy functions to solve the other combinatorial optimization problems.In this paper, we redefine the quartic form energy function to be able to apply not only TSPs but also Quadratic Assign Problems (QAP). After that we show that the ID network has only global minima, which are located on the vertices of the output space, as the stationary states, and the parameter region is discussed.