A RIGOROUS COMPUTATIONAL COMPARISON OF ALTERNATIVE SOLUTION METHODS FOR THE GENERALIZED ASSIGNMENT PROBLEM

Statistical experimental design and analysis is a cornerstone for scie ntific inquiry that is rarely applied in reporting computational testi ng. This approach is employed to study the relative performance charac teristics of the four leading algorithmic and heuristic alternatives t o 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 meth odologies and VDSH under the effects of various problem characteristic s, we devise a carefully designed experimentation of state-of-the-art implementations; through a rigorous statistical analysis we identify t he most efficient method(s) for commonly studied LCGAPs, and determine the effect on solution time and quality of problem class and size.