Theoretical insights into the augmented-neural-network approach for combinatorial optimization

The augmented-neural-network (AugNN) approach has been applied lately to some NP-Hard combinatorial problems, such as task scheduling, open-shop scheduling and resource-constraint project scheduling. In this approach the problem of search in the solution-space is transformed to a search in a weight-matrix space, much like in a neural-network approach. Some weight adjustment strategies are then used to converge to a good set of weights for a locally optimal solution. While empirical results have demonstrated the effectiveness of the AugNN approach vis-à-vis a few other metaheuristics, little theoretical insights exist which justify this approach and explain the effectiveness thereof. This paper provides some theoretical insights and justification for the AugNN approach through some basic theorems and also describes the algorithm and the formulation with the help of examples.