IDEAS home Printed from https://ideas.repec.org/a/ids/ijisen/v3y2008i5p530-548.html
   My bibliography  Save this article

Exploiting empirical knowledge for bi-dimensional knapsack problem heuristics

Author

Listed:
  • Yong Kun Cho
  • James T. Moore
  • Raymond R. Hill
  • Charles H. Reilly

Abstract

The Multidimensional Knapsack Problem (MKP) has been used to model a variety of practical applications. Due to its combinatorial nature, heuristics are often employed to quickly find good solutions to MKPs. There have been a variety of heuristics proposed for MKP and a plethora of empirical studies comparing the performance of these heuristics. However, little has been done to garner a deeper understanding of why certain heuristics perform well on certain types of problems and others do not. Using a broad range of practical MKP test problems, we use three representative heuristics and conduct an empirical study aimed at gaining a deeper understanding of heuristic procedure performance as a function of test problem constraint characteristics. Our focus is on the Two-dimensional Knapsack Problem (2KP). New insights developed regarding greedy heuristic performance are exploited to yield two new heuristics whose performance is more robust than that of three legacy heuristics on our test problem set and on benchmark sets of MKP problems. A competitive test of these new heuristics against a set of legacy heuristics, using both existing test problem sets and a new systematically developed test problem set demonstrate the superior, robust performance of our new heuristics.

Suggested Citation

  • Yong Kun Cho & James T. Moore & Raymond R. Hill & Charles H. Reilly, 2008. "Exploiting empirical knowledge for bi-dimensional knapsack problem heuristics," International Journal of Industrial and Systems Engineering, Inderscience Enterprises Ltd, vol. 3(5), pages 530-548.
    • Handle: RePEc:ids:ijisen:v:3:y:2008:i:5:p:530-548
    as

    Download full text from publisher

    File URL: http://www.inderscience.com/link.php?id=18231
    Download Restriction: Access to full text is restricted to subscribers.
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Mohamad Alissa & Kevin Sim & Emma Hart, 2023. "Automated Algorithm Selection: from Feature-Based to Feature-Free Approaches," Journal of Heuristics, Springer, vol. 29(1), pages 1-38, February.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:ids:ijisen:v:3:y:2008:i:5:p:530-548. See general information about how to correct material in RePEc.

    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.

    We have no bibliographic references for this item. You can help adding them by using 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 RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sarah Parker (email available below). General contact details of provider: http://www.inderscience.com/browse/index.php?journalID=188 .

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

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.