Yet another "optimal" neural representation for combinatorial optimization

On a theoretical basis, two "optimal" neural representations were already presented for many combinatorial optimization problems. However, one is only for combinatorial optimization problems with a linear cost function [S. Matsuda, 1995], and other is applicable to quadratic combinatorial optimization problems but is higher order and needs a Hopfield network of higher order to implement [M. Takeda et al., 1986]. Higher order Hopfield networks are very time-consuming, so it is desirable that we have another "optimal" neural representation that overcomes the above weakness. In this paper, taking traveling salesman problems and assignment problems as examples, we present such an "optimal" neural representation. This neural representation is applicable even to quadratic combinatorial optimization problems, is not of higher order, and does not employ higher order Hopfield networks to implement. In the same manner we can design the "optimal" neural representations for many combinatorial optimization problems, including quadratic ones. Finally, simulations are made to illustrate the effectiveness.