IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v254y2016i2p398-409.html
   My bibliography  Save this article

Robust efficiency measures for linear knapsack problem variants

Author

Listed:
  • Wishon, Christopher
  • Villalobos, J. Rene

Abstract

Numerous combinatorial optimization applications, such as the mobile retailer product mix problem, utilize the multidemand, multidimensional knapsack problem variant in which there are multiple knapsack constraints requiring a weighted summation of the variables to be less than or equal to a nonnegative value and multiple demand constraints requiring a weighted summation of the variables to be greater than or equal to a nonnegative value. The purpose of this paper is to demonstrate that core variables and efficiency measures, concepts used in the most efficient solvers to-date for binary knapsack problems and some of its variants, can be extended to the multidemand, multidimensional knapsack problem variant. Specifically, new efficiency measure calculations are provided and their properties are mathematically proven and experimentally demonstrated. The contribution of such measures to knapsack problem research is that these measures are applicable to all knapsack problem variants with a single linear objective function and linear constraints of any quantity. The applicability of these new measures is demonstrated through the development of three heuristic procedures: a Fixed-Core heuristic, a Genetic Algorithm, and a Kernel Search heuristic. The results from these tests are compared with the results from a commercial solver and an existing heuristic. The findings from these tests demonstrate that the Fixed-Core and Kernel Search heuristics developed for this paper are the most efficient solvers to-date for hard multidemand, multidimensional knapsack problems.

Suggested Citation

  • Wishon, Christopher & Villalobos, J. Rene, 2016. "Robust efficiency measures for linear knapsack problem variants," European Journal of Operational Research, Elsevier, vol. 254(2), pages 398-409.
    • Handle: RePEc:eee:ejores:v:254:y:2016:i:2:p:398-409
    DOI: 10.1016/j.ejor.2016.04.025
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221716302442
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2016.04.025?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

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

    References listed on IDEAS

    as
    1. Paola Cappanera & Marco Trubian, 2005. "A Local-Search-Based Heuristic for the Demand-Constrained Multidimensional Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 17(1), pages 82-98, February.
    2. Dudzinski, Krzysztof & Walukiewicz, Stanislaw, 1987. "Exact methods for the knapsack problem and its generalizations," European Journal of Operational Research, Elsevier, vol. 28(1), pages 3-21, January.
    3. Egon Balas & Eitan Zemel, 1980. "An Algorithm for Large Zero-One Knapsack Problems," Operations Research, INFORMS, vol. 28(5), pages 1130-1154, October.
    4. Silvano Martello & Paolo Toth, 1988. "A New Algorithm for the 0-1 Knapsack Problem," Management Science, INFORMS, vol. 34(5), pages 633-644, May.
    5. David Pisinger, 1997. "A Minimal Algorithm for the 0-1 Knapsack Problem," Operations Research, INFORMS, vol. 45(5), pages 758-767, October.
    6. Ang, James S.K. & Cao, Chengxuan & Ye, Heng-Qing, 2007. "Model and algorithms for multi-period sea cargo mix problem," European Journal of Operational Research, Elsevier, vol. 180(3), pages 1381-1393, August.
    7. Pisinger, David, 1995. "An expanding-core algorithm for the exact 0-1 knapsack problem," European Journal of Operational Research, Elsevier, vol. 87(1), pages 175-187, November.
    8. Mavrotas, George & Figueira, José Rui & Florios, Kostas, 2009. "Solving the bi-objective multidimensional knapsack problem exploiting the concept of core," MPRA Paper 105087, University Library of Munich, Germany.
    9. George B. Dantzig, 1957. "Discrete-Variable Extremum Problems," Operations Research, INFORMS, vol. 5(2), pages 266-288, April.
    10. Jakob Puchinger & Günther R. Raidl & Ulrich Pferschy, 2010. "The Multidimensional Knapsack Problem: Structure and Algorithms," INFORMS Journal on Computing, INFORMS, vol. 22(2), pages 250-265, May.
    11. David Pisinger, 2000. "A Minimal Algorithm for the Bounded Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 12(1), pages 75-82, February.
    12. Pisinger, David, 1995. "A minimal algorithm for the multiple-choice knapsack problem," European Journal of Operational Research, Elsevier, vol. 83(2), pages 394-410, June.
    13. Silvano Martello & Paolo Toth, 1997. "Upper Bounds and Algorithms for Hard 0-1 Knapsack Problems," Operations Research, INFORMS, vol. 45(5), pages 768-778, October.
    14. Gregory Dobson, 1982. "Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data," Mathematics of Operations Research, INFORMS, vol. 7(4), pages 515-531, November.
    15. David Pisinger, 1999. "Core Problems in Knapsack Algorithms," Operations Research, INFORMS, vol. 47(4), pages 570-575, August.
    16. Silvano Martello & David Pisinger & Paolo Toth, 1999. "Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem," Management Science, INFORMS, vol. 45(3), pages 414-424, March.
    17. Martello, Silvano & Pisinger, David & Toth, Paolo, 2000. "New trends in exact algorithms for the 0-1 knapsack problem," European Journal of Operational Research, Elsevier, vol. 123(2), pages 325-332, June.
    Full references (including those not matched with items on IDEAS)

    Citations

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


    Cited by:

    1. del Castillo, Enrique & Beretta, Alessia & Semeraro, Quirico, 2017. "Optimal setup of a multihead weighing machine," European Journal of Operational Research, Elsevier, vol. 259(1), pages 384-393.
    2. Lai, Xiangjing & Hao, Jin-Kao & Yue, Dong, 2019. "Two-stage solution-based tabu search for the multidemand multidimensional knapsack problem," European Journal of Operational Research, Elsevier, vol. 274(1), pages 35-48.
    3. Rafael García-Jiménez & J. Carlos García-Díaz & Alexander D. Pulido-Rojano, 2021. "Packaging Process Optimization in Multihead Weighers with Double-Layered Upright and Diagonal Systems," Mathematics, MDPI, vol. 9(9), pages 1-20, May.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Mavrotas, George & Florios, Kostas & Figueira, José Rui, 2015. "An improved version of a core based algorithm for the multi-objective multi-dimensional knapsack problem: A computational study and comparison with meta-heuristics," Applied Mathematics and Computation, Elsevier, vol. 270(C), pages 25-43.
    2. Jakob Puchinger & Günther R. Raidl & Ulrich Pferschy, 2010. "The Multidimensional Knapsack Problem: Structure and Algorithms," INFORMS Journal on Computing, INFORMS, vol. 22(2), pages 250-265, May.
    3. Arnaud Fréville & SaÏd Hanafi, 2005. "The Multidimensional 0-1 Knapsack Problem—Bounds and Computational Aspects," Annals of Operations Research, Springer, vol. 139(1), pages 195-227, October.
    4. Charles H. Reilly, 2009. "Synthetic Optimization Problem Generation: Show Us the Correlations!," INFORMS Journal on Computing, INFORMS, vol. 21(3), pages 458-467, August.
    5. Sbihi, Abdelkader, 2010. "A cooperative local search-based algorithm for the Multiple-Scenario Max-Min Knapsack Problem," European Journal of Operational Research, Elsevier, vol. 202(2), pages 339-346, April.
    6. Mhand Hifi & Hedi Mhalla & Slim Sadfi, 2005. "Sensitivity of the Optimum to Perturbations of the Profit or Weight of an Item in the Binary Knapsack Problem," Journal of Combinatorial Optimization, Springer, vol. 10(3), pages 239-260, November.
    7. Silvano Martello & Paolo Toth, 2003. "An Exact Algorithm for the Two-Constraint 0--1 Knapsack Problem," Operations Research, INFORMS, vol. 51(5), pages 826-835, October.
    8. M Hifi & M Michrafy & A Sbihi, 2004. "Heuristic algorithms for the multiple-choice multidimensional knapsack problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(12), pages 1323-1332, December.
    9. Silvano Martello & David Pisinger & Paolo Toth, 1999. "Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem," Management Science, INFORMS, vol. 45(3), pages 414-424, March.
    10. Pisinger, David, 1995. "A minimal algorithm for the multiple-choice knapsack problem," European Journal of Operational Research, Elsevier, vol. 83(2), pages 394-410, June.
    11. Reilly, Charles H. & Sapkota, Nabin, 2015. "A family of composite discrete bivariate distributions with uniform marginals for simulating realistic and challenging optimization-problem instances," European Journal of Operational Research, Elsevier, vol. 241(3), pages 642-652.
    12. Nicholas G. Hall & Marc E. Posner, 2007. "Performance Prediction and Preselection for Optimization and Heuristic Solution Procedures," Operations Research, INFORMS, vol. 55(4), pages 703-716, August.
    13. Abdelkader Sbihi, 2007. "A best first search exact algorithm for the Multiple-choice Multidimensional Knapsack Problem," Journal of Combinatorial Optimization, Springer, vol. 13(4), pages 337-351, May.
    14. Mhand Hifi & Slim Sadfi & Abdelkader Sbihi, 2004. "An Exact Algorithm for the Multiple-choice Multidimensional Knapsack Problem," Post-Print halshs-03322716, HAL.
    15. David Pisinger, 1999. "Core Problems in Knapsack Algorithms," Operations Research, INFORMS, vol. 47(4), pages 570-575, August.
    16. Ghosh, Diptesh & Bandyopadhyay, Tathagata, 2006. "Spotting Difficult Weakly Correlated Binary Knapsack Problems," IIMA Working Papers WP2006-01-04, Indian Institute of Management Ahmedabad, Research and Publication Department.
    17. Toth, Paolo, 2000. "Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems," European Journal of Operational Research, Elsevier, vol. 125(2), pages 222-238, September.
    18. Mhand Hifi & Slim Sadfi & Abdelkader Sbihi, 2004. "An Exact Algorithm for the Multiple-choice Multidimensional Knapsack Problem," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) halshs-03322716, HAL.
    19. Al-Shihabi, Sameh, 2021. "A Novel Core-Based Optimization Framework for Binary Integer Programs- the Multidemand Multidimesional Knapsack Problem as a Test Problem," Operations Research Perspectives, Elsevier, vol. 8(C).
    20. Mavrotas, George & Figueira, José Rui & Florios, Kostas, 2009. "Solving the bi-objective multidimensional knapsack problem exploiting the concept of core," MPRA Paper 105087, University Library of Munich, Germany.

    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:eee:ejores:v:254:y:2016:i:2:p:398-409. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc 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 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.