A Very Large-Scale Neighborhood Search Algorithm for the Multi-Resource Generalized Assignment Problem

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.

Key Words: multi-resource generalized assignment problem, ejection chain, very large-scale neighborhood search, adaptive parameter adjustment, strategic oscillation

Discrete Optimization, 1 (2004) 87-98.

Back to the Paper List