Journal article
A reduction approach to the repeated assignment problem
Department of Computer Science, The National Defense Academy, Yokosuka, Kanagawa 239-8686, Japan1
OR&M Group, Faculty of Economics and Econometrics, University of Amsterdam, The Netherlands2
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.
Language: | English |
---|---|
Year: | 2011 |
Pages: | 185-193 |
ISSN: | 18726860 and 03772217 |
Types: | Journal article |
DOI: | 10.1016/j.ejor.2010.10.027 |