A Rigorous Computational Comparison of Alternative Solution Methods for the Generalized Assignment Problem

Statistical experimental design and analysis is a cornerstone for scientific inquiry that is rarely applied in reporting computational testing. This approach is employed to study the relative performance characteristics of the four leading algorithmic and heuristic alternatives to solve the Linear Cost Generalized Assignment Problem (LCGAP) against a newly developed heuristic, Variable-Depth Search Heuristic (VDSH). In assessing the relative effectiveness of the prominent solution methodologies and VDSH under the effects of various problem characteristics, we devise a carefully designed experimentation of state-of-the-art implementations; through a rigorous statistical analysis we identify the most efficient method(s) for commonly studied LCGAPs, and determine the effect on solution time and quality of problem class and size.