A parallel implementation to the multidimensional knapsack problem using augmented neural networks

The knapsack problem is a widely known problem in combinatorial optimization and has been object of many researches in the last decades. The problem has a great number of variants and obtaining an exact solution to any of these is not easily accomplished, which motivates the search for alternative techniques to solve the problem. Among these alternatives, augmented neural networks seem to be suitable on the search for approximate solutions for the problem. In this work we propose a parallel implementation for the multidimensional knapsack problem using augmented neural networks. The obtained results show that augmented neural networks allow efficient parallelization using CUDA: even smaller numbers of epoques resulted on equal or even better solutions than the sequential implementation. Differently, MPI implementation did not achieve satisfactory results.