Orthogonal projections applied to the assignment problem

This paper presents a significant improvement to the traditional neural approach to the assignment problem (AP). The technique is based on identifying the feasible space (F) with a linear subspace of R(n²), and then analyzing the orthogonal projection onto F. The formula for the orthogonal projection is shown to be simple and easy to integrate into the traditional neural model. This projection concept was first developed by Wolfe et al. (1993), but here we show that the projection can be computed in a much simpler way, and that the addition of a “clip” operator at the boundaries of the cube can improve the results by an order of magnitude in both accuracy and run time. It is proven that the array of numbers that define an AP can be projected onto F without loss of information and the network can be constrained to operate exclusively in F until a neuron is saturated (i.e., reaches the maximum or minimum activation). Two “clip” options are presented and compared. Statistical results are presented for randomly generated APs of sizes n=10 to n=50. The statistics confirm the theory