Department of Applied Mathematics & Physics, Kyoto Univiversity

Technical Report #99013 (June, 1999)

An Ejection Chain Approach for the Generalized Assignment Problem
by Mutsunori Yagiura, Toshihide Ibaraki and Fred Glover

We propose a tabu search algorithm for the generalized assignment problem, which is one of the representative combinatorial optimization problems known to be NP-hard. The algorithm features an ejection chain approach, which is embedded in a neighborhood construction to create more complex and powerful moves. We also incorporate an automatic mechanism for adjusting search parameters, to maintain a balance between visits to feasible and infeasible regions. Computational comparisons on benchmark instances show that the method obtain solutions that are optimal or that deviate by at most 0.16% from the best solutions obtained by an exact method, for problems small enough for the exact method to handle. For larger problems, our method obtains solutions for all problems better than the best obtained by all other heuristics tested.