An Ejection Chain Approach for the Generalized Assignment Problem

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 of small sizes show that the method obtain solutions that are optimal or that deviate by at most 0.16% from the best known solutions. For instances of larger sizes, our method obtains best solutions among all heuristics tested.

Key Words: automatic parameter adjustment, ejection chain, generalized assignment problem, local search, metaheuristics, tabu search

INFORMS Journal on Computing, 16 (2004) 133-151.

Erratum: p. 136, the first line of formula (3). The minus before the last term should be plus.
Back to the Paper List