A reduction approach to the repeated assignment problem |
| |
Authors: | Daisuke Yokoya Cees W Duin Takeo Yamada |
| |
Institution: | 1. Department of Computer Science, The National Defense Academy, Yokosuka, Kanagawa 239-8686, Japan;2. OR&M Group, Faculty of Economics and Econometrics, University of Amsterdam, The Netherlands |
| |
Abstract: | 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. |
| |
Keywords: | Repeated assignment problem Combinatorial optimization Relaxation Pegging test |
本文献已被 ScienceDirect 等数据库收录! |
|