Improved projection Hopfield network for the quadratic assignment problem

The continuous-valued Hopfield neural network (CHN) is a popular method of metaheuristics. However, it is not guaranteed that obtained solutions by the CHN are always feasible. To obtain a high-quality feasible solution, appropriate penalty parameters of CHN are required. Matsuda has shown the theoretical relationship between penalty parameters and the qualities of obtained solutions of the CHN for a traveling salesman problem (TSP). We show a similar theoretical relationship of the CHN for the quadratic assignment problem (QAP) and the limitation of the CHP. On other hand, Smith et al. proposed the projection method to obtain a high-quality feasible solution, which projects a modified solution onto two constraints, by turns. Thus, this method is not efficient and does not necessarily find a feasible solution at each iteration. Therefore, we propose a new method with the projection of a modified solution onto the entire feasible region at once. Moreover, we show convergence properties of the proposed method and the conditions of penalty parameters which guarantees that the CHN for QAP always finds the feasible solution. Finally, we verify the efficiency of the methods through numerical experiments.