A neural algorithm incorporating winner‐take‐all subnets for combinatorial optimization

Using a neural net composed of subnets with a winner‐take‐all (WTA) mode of operations, the constraint that the variables must form a probability vector or a probability matrix can automatically be satisfied. Taking advantage of this property, this paper proposes a neural algorithm than can derive the approximate solution for a combinatorial optimization problem such as set partitioning. As a simple example, the 3‐partition maximum‐cut problem is considered. The worst‐case error is evaluated theoretically, and it is shown that the proposed method is one‐third (relative) approximate algorithm. For comparison, the performance of the conventional method also is evaluated theoretically. The performances also are compared by experiment. Both the theoretical and experimental results confirm that the proposed method can achieve better performance than the conventional method.