IDEAS home Printed from
MyIDEAS: Log in (now much improved!) to save this article

The Effects of Coefficient Correlation Structure in Two-Dimensional Knapsack Problems on Solution Procedure Performance

Listed author(s):
  • Raymond R. Hill


    (Air Force Institute of Technology, AFIT/ENS, Building 640, 2950 P Street, Wright-Patterson Air Force Base, Ohio 45433-7765)

  • Charles H. Reilly


    (Department of Industrial Engineering and Management Systems, University of Central Florida, 4000 Central Florida Boulevard, P.O. Box 162450, Orlando, Florida 32816-2450)

Registered author(s):

    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.

    If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.

    File URL:
    Download Restriction: no

    Article provided by INFORMS in its journal Management Science.

    Volume (Year): 46 (2000)
    Issue (Month): 2 (February)
    Pages: 302-317

    in new window

    Handle: RePEc:inm:ormnsc:v:46:y:2000:i:2:p:302-317
    Contact details of provider: Postal:
    7240 Parkway Drive, Suite 300, Hanover, MD 21076 USA

    Phone: +1-443-757-3500
    Fax: 443-757-3515
    Web page:

    More information through EDIRC

    References listed on IDEAS
    Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:

    in new window

    1. Frieze, A. M. & Clarke, M. R. B., 1984. "Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses," European Journal of Operational Research, Elsevier, vol. 15(1), pages 100-109, January.
    2. Egon Balas & Clarence H. Martin, 1980. "Pivot and Complement--A Heuristic for 0-1 Programming," Management Science, INFORMS, vol. 26(1), pages 86-96, January.
    3. Marshall L. Fisher & R. Jaikumar & Luk N. Van Wassenhove, 1986. "A Multiplier Adjustment Method for the Generalized Assignment Problem," Management Science, INFORMS, vol. 32(9), pages 1095-1103, September.
    4. Stelios H. Zanakis, 1977. "Heuristic 0-1 Linear Programming: An Experimental Comparison of Three Methods," Management Science, INFORMS, vol. 24(1), pages 91-104, September.
    5. Lokketangen, Arne & Glover, Fred, 1998. "Solving zero-one mixed integer programming problems using tabu search," European Journal of Operational Research, Elsevier, vol. 106(2-3), pages 624-658, April.
    6. C. N. Potts & L. N. Van Wassenhove, 1988. "Algorithms for Scheduling a Single Machine to Minimize the Weighted Number of Late Jobs," Management Science, INFORMS, vol. 34(7), pages 843-858, July.
    7. Freville, Arnaud & Plateau, Gerard, 1993. "An exact search for the solution of the surrogate dual of the 0-1 bidimensional knapsack problem," European Journal of Operational Research, Elsevier, vol. 68(3), pages 413-421, August.
    8. Mohammad M. Amini & Michael Racer, 1994. "A Rigorous Computational Comparison of Alternative Solution Methods for the Generalized Assignment Problem," Management Science, INFORMS, vol. 40(7), pages 868-890, July.
    9. Yoshiaki Toyoda, 1975. "A Simplified Algorithm for Obtaining Approximate Solutions to Zero-One Programming Problems," Management Science, INFORMS, vol. 21(12), pages 1417-1427, August.
    Full references (including those not matched with items on IDEAS)

    This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.

    When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:46:y:2000:i:2:p:302-317. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Mirko Janc)

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If references are entirely missing, you can add them using this form.

    If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    This information is provided to you by IDEAS at the Research Division of the Federal Reserve Bank of St. Louis using RePEc data.