The effects of coefficient correlation structure in two-dimensional knapsack problems on solution procedure performance

    Authors

    R. R. Hill;C. H. Reilly

    Abbreviated Journal Title

    Manage. Sci.

    Keywords

    product moment correlation induction; rank correlation induction; computational testing of algorithms/heuristics; empirical analysis of; algorithms/heuristics; bidimensional knapsack problem; test problem; generation; GENERALIZED ASSIGNMENT PROBLEM; SINGLE-MACHINE; PROGRAMMING-PROBLEMS; TABU SEARCH; ALGORITHMS; MINIMIZE; Management; Operations Research & Management Science

    Abstract

    This paper presents the results of an empirical study of the effects of coefficient correlation structure and constraint slackness settings on the performance of solution procedures on synthetic two-dimensional knapsack problems (2KP). The population correlation structure among 2KP coefficients, the level of constraint slackness, and the type of correlation (product moment or rank) are varied in this study. Representative branch-and-bound and heuristic solution procedures are used to investigate the influence of these problem parameters on solution procedure performance. Population correlation structure, and in particular the interconstraint component of the correlation structure, is found to be a significant factor influencing the performance of both the algorithm and the heuristic. In addition, the interaction between constraint slackness and population correlation structure is found to influence solution procedure performance.

    Journal Title

    Management Science

    Volume

    46

    Issue/Number

    2

    Publication Date

    1-1-2000

    Document Type

    Article

    Language

    English

    First Page

    302

    Last Page

    317

    WOS Identifier

    WOS:000086130700009

    ISSN

    0025-1909

    Share

    COinS