Department of Applied Mathematics & Physics, Kyoto University
Technical Report 2004-003 (March 09, 2004)
A Very Large-Scale Neighborhood Search Algorithm for the Multi-Resource Generalized Assignment Problem
by Mutsunori Yagiura, Shinji Iwasaki, Toshihide Ibaraki and Fred Glover
We propose a metaheuristic algorithm for the multi-resource generalized assignment problem (MRGAP). MRGAP is a generalization of the
generalized assignment problem, which is one of the representative combinatorial optimization problems known to be NP-hard. The algorithm
features a very large-scale neighborhood search, which is a mechanism of conducting the search with complex and powerful moves, where the
resulting neighborhood is efficiently searched via the improvement graph. We also incorporate an adaptive 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 is effective, especially for type D and E instances, which are known to be quite difficult.