An investigation of the relationship between problem characteristics and algorithm performance: a case study of the GAP

    Authors

    M. C. Cario; J. J. Clifford; R. R. Hill; J. W. Yang; K. J. Yang;C. H. Reilly

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    IIE Trans.

    Keywords

    GENERALIZED ASSIGNMENT PROBLEM; KNAPSACK-PROBLEMS; SINGLE-MACHINE; Engineering, Industrial; Operations Research & Management Science

    Abstract

    We compare synthetic Generalized Assignment Problems (GAP) generated under two correlation-induction strategies: Implicit Correlation Induction (ICI) and Explicit Correlation Induction (ECI). We present computational results for two commercially-available solvers and four heuristics on 590 test problems. We conclude that the solvers' performances degrade as the population correlation between the objective function and capacity constraint coefficients decreases. However, the heuristics' performances improved as the absolute value of the same population correlation increases. We find that problems generated under ECI are more challenging than problems generated under ICI and may lead to a better understanding of the capabilities and limitations of the solution methods being evaluated. We recommend that one consider the purpose (s) of an experiment and types of solution procedures to be evaluated when determining what types of test problems to generate.

    Journal Title

    Iie Transactions

    Volume

    34

    Issue/Number

    3

    Publication Date

    1-1-2002

    Document Type

    Article

    Language

    English

    First Page

    297

    Last Page

    312

    WOS Identifier

    WOS:000171486000008

    ISSN

    0740-817X

    Share

    COinS