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

PostScript File

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.