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

Features for the 0-1 knapsack problem based on inclusionwise maximal solutions

Author

Listed:
  • Jooken, Jorik
  • Leyman, Pieter
  • De Causmaecker, Patrick

Abstract

Decades of research on the 0-1 knapsack problem led to very efficient algorithms that are able to quickly solve large problem instances to optimality. This prompted researchers to also investigate the structure of problem instances that are hard for existing solvers. In the current paper we are interested in investigating which features make 0-1 knapsack problem instances hard to solve to optimality for the state-of-the-art 0-1 knapsack solver. We propose a set of 14 features based on previous work by the authors in which so-called inclusionwise maximal solutions (IMSs) play a central role. Calculating these features is computationally expensive and requires one to solve hard combinatorial problems. Based on new structural results about IMSs, we formulate polynomial and pseudopolynomial time algorithms for calculating these features. These algorithms were executed for two large datasets on a supercomputer in approximately 540 CPU-hours. We show that the proposed features contain important information related to the empirical hardness of a problem instance that was missing in earlier features from the literature by training machine learning models that can accurately predict the empirical hardness of a wide variety of 0-1 knapsack problem instances. Moreover, we show that these features can be cheaply approximated at the cost of less accurate hardness predictions. Using the instance space analysis methodology, we show that hard 0-1 knapsack problem instances are clustered together around a relatively dense region of the instance space and several features behave differently in the easy and hard parts of the instance space.

Suggested Citation

  • Jooken, Jorik & Leyman, Pieter & De Causmaecker, Patrick, 2023. "Features for the 0-1 knapsack problem based on inclusionwise maximal solutions," European Journal of Operational Research, Elsevier, vol. 311(1), pages 36-55.
  • Handle: RePEc:eee:ejores:v:311:y:2023:i:1:p:36-55
    DOI: 10.1016/j.ejor.2023.04.023
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221723003065
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2023.04.023?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. Dimitris Achlioptas & Assaf Naor & Yuval Peres, 2005. "Rigorous location of phase transitions in hard optimization problems," Nature, Nature, vol. 435(7043), pages 759-764, June.
    2. Zonghao Gu & George L. Nemhauser & Martin W. P. Savelsbergh, 1999. "Lifted Cover Inequalities for 0-1 Integer Programs: Complexity," INFORMS Journal on Computing, INFORMS, vol. 11(1), pages 117-123, February.
    3. Raymond R. Hill & Charles H. Reilly, 2000. "The Effects of Coefficient Correlation Structure in Two-Dimensional Knapsack Problems on Solution Procedure Performance," Management Science, INFORMS, vol. 46(2), pages 302-317, February.
    4. Coniglio, Stefano & Furini, Fabio & San Segundo, Pablo, 2021. "A new combinatorial branch-and-bound algorithm for the Knapsack Problem with Conflicts," European Journal of Operational Research, Elsevier, vol. 289(2), pages 435-455.
    5. Andonov, R. & Poirriez, V. & Rajopadhye, S., 2000. "Unbounded knapsack problem: Dynamic programming revisited," European Journal of Operational Research, Elsevier, vol. 123(2), pages 394-407, June.
    6. Jooken, Jorik & Leyman, Pieter & De Causmaecker, Patrick, 2022. "A new class of hard problem instances for the 0–1 knapsack problem," European Journal of Operational Research, Elsevier, vol. 301(3), pages 841-854.
    7. George B. Dantzig, 1957. "Discrete-Variable Extremum Problems," Operations Research, INFORMS, vol. 5(2), pages 266-288, April.
    8. 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.
    9. C R Reeves & A V Eremeev, 2004. "Statistical analysis of local search landscapes," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(7), pages 687-693, July.
    10. David Pisinger, 2000. "A Minimal Algorithm for the Bounded Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 12(1), pages 75-82, February.
    11. Martello, Silvano & Toth, Paolo, 1977. "An upper bound for the zero-one knapsack problem and a branch and bound algorithm," European Journal of Operational Research, Elsevier, vol. 1(3), pages 169-175, May.
    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. Liu, Chang & Smith-Miles, Kate & Wauters, Tony & Costa, Alysson M., 2024. "Instance space analysis for 2D bin packing mathematical models," European Journal of Operational Research, Elsevier, vol. 315(2), pages 484-498.

    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. Leo Lopes & Kate Smith-Miles, 2013. "Generating Applicable Synthetic Instances for Branch Problems," Operations Research, INFORMS, vol. 61(3), pages 563-577, June.
    2. Jooken, Jorik & Leyman, Pieter & De Causmaecker, Patrick, 2022. "A new class of hard problem instances for the 0–1 knapsack problem," European Journal of Operational Research, Elsevier, vol. 301(3), pages 841-854.
    3. 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.
    4. 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.
    5. 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.
    6. Freville, Arnaud, 2004. "The multidimensional 0-1 knapsack problem: An overview," European Journal of Operational Research, Elsevier, vol. 155(1), pages 1-21, May.
    7. Marc Goerigk, 2014. "A note on upper bounds to the robust knapsack problem with discrete scenarios," Annals of Operations Research, Springer, vol. 223(1), pages 461-469, December.
    8. 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.
    9. Pasquale Avella & Maurizio Boccia & Igor Vasilyev, 2012. "Computational Testing of a Separation Procedure for the Knapsack Set with a Single Continuous Variable," INFORMS Journal on Computing, INFORMS, vol. 24(1), pages 165-171, February.
    10. Iida, Hiroshi, 2011. "How to solve the collapsing subset-sum problem revisited," ビジネス創造センターディスカッション・ペーパー (Discussion papers of the Center for Business Creation) 10252/4432, Otaru University of Commerce.
    11. Viet Anh Nguyen & Fan Zhang & Shanshan Wang & Jose Blanchet & Erick Delage & Yinyu Ye, 2021. "Robustifying Conditional Portfolio Decisions via Optimal Transport," Papers 2103.16451, arXiv.org, revised Apr 2024.
    12. Jeff Kahn & Gil Kalai, 2006. "Thresholds and expectation thresholds," Levine's Bibliography 122247000000001294, UCLA Department of Economics.
    13. Herweg, Fabian & Müller, Daniel, 2008. "The Optimality of Simple Contracts: Moral Hazard and Loss Aversion," Bonn Econ Discussion Papers 17/2008, University of Bonn, Bonn Graduate School of Economics (BGSE).
    14. Mhand Hifi & Slim Sadfi & Abdelkader Sbihi, 2004. "An Exact Algorithm for the Multiple-choice Multidimensional Knapsack Problem," Post-Print halshs-03322716, HAL.
    15. B. Golany & N. Goldberg & U. Rothblum, 2015. "Allocating multiple defensive resources in a zero-sum game setting," Annals of Operations Research, Springer, vol. 225(1), pages 91-109, February.
    16. Albert H. Schrotenboer & Evrim Ursavas & Iris F. A. Vis, 2019. "A Branch-and-Price-and-Cut Algorithm for Resource-Constrained Pickup and Delivery Problems," Transportation Science, INFORMS, vol. 53(4), pages 1001-1022, July.
    17. Teresa Estañ & Natividad Llorca & Ricardo Martínez & Joaquín Sánchez-Soriano, 2020. "On the difficulty of budget allocation in claims problems with indivisible items of different prices," ThE Papers 20/09, Department of Economic Theory and Economic History of the University of Granada..
    18. Liang Chen & Wei-Kun Chen & Mu-Ming Yang & Yu-Hong Dai, 2021. "An exact separation algorithm for unsplittable flow capacitated network design arc-set polyhedron," Journal of Global Optimization, Springer, vol. 81(3), pages 659-689, November.
    19. David Pisinger, 1999. "Core Problems in Knapsack Algorithms," Operations Research, INFORMS, vol. 47(4), pages 570-575, August.
    20. Teresa Estañ & Natividad Llorca & Ricardo Martínez & Joaquín Sánchez-Soriano, 2021. "On the Difficulty of Budget Allocation in Claims Problems with Indivisible Items and Prices," Group Decision and Negotiation, Springer, vol. 30(5), pages 1133-1159, October.

    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:311:y:2023:i:1:p:36-55. 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.