Heuristic and exact algorithms for the simultaneous assignment problem

The simultaneous assignment problem is formulated as an extension to the assignment problem. The problem is proved NP-hard. We evaluate its lower bound and present some approximate algorithms. Also we introduce the pegging test to this problem and show that this remarkably reduces the size of the original problem. Combining these we give an algorithm to solve the problem to optimality, and through numerical tests analyze the behavior of the developed algorithms. Randomly generated test problems with up to 48000 variables are solved in less than a few minutes.