A reduction approach to the repeated assignment problem

被引:1
作者
Yokoya, Daisuke [1 ]
Duin, Cees W. [2 ]
Yamada, Takeo [1 ]
机构
[1] Natl Def Acad, Dept Comp Sci, Kanagawa 2398686, Japan
[2] Univ Amsterdam, OR&M Grp, Fac Econ & Econometr, NL-1012 WX Amsterdam, Netherlands
关键词
Repeated assignment problem; Combinatorial optimization; Relaxation; Pegging test;
D O I
10.1016/j.ejor.2010.10.027
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
We consider the repeated assignment problem (RAP), which is a K-fold repetition of the n x 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. (C) 2010 Elsevier B.V. All rights reserved.
引用
收藏
页码:185 / 193
页数:9
相关论文
共 26 条
  • [1] Ahuja R., 1993, NETWORK FLOWS THEORY
  • [2] [Anonymous], COMMUNICATIONS OR SO
  • [3] [Anonymous], ILOG CPLEX 11 1
  • [4] [Anonymous], COMPUTERS OPERATIONS
  • [5] [Anonymous], P 2 INT C DISCR OPT
  • [6] [Anonymous], P IEEE INFOCOM
  • [7] [Anonymous], 2003, COMBINATORIAL OPTIMI
  • [8] [Anonymous], 1979, JOHNSON COMPUTERS IN
  • [9] [Anonymous], 2007, J. Appl. Industr. Math, DOI DOI 10.1134/S1990478907040072
  • [10] Burkard R., 2009, ASSIGNMENT PROBLEMS