A reduction approach to the repeated assignment problem

We consider the repeated assignment problem (RAP), which is a K-fold repetition of the n×n linear assignment problem (LAP), with the additional requirement that no assignment can be repeated more than once. In actual applications K is typically much smaller than n. First, we derive upper and lower bounds respectively by a heuristic together with local search, and an efficient method solving the continuous relaxation.

The latter also solves a Lagrangian relaxation, such that the related pegging test, to fix variables at zero or one, decomposes into K independent pegging tests to LAPs. These can be solved exactly by transforming them into all-pairs shortest path problems. Together with these procedures, we also employ a virtual pegging test and reduce RAP in size.

Numerical experiments show that the reduced instances, with K≪n, can be solved exactly using standard MIP solvers.