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.