IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v40y2020i1d10.1007_s10878-020-00584-2.html
   My bibliography  Save this article

Analysis of Divide-and-Conquer strategies for the 0–1 minimization knapsack problem

Author

Listed:
  • Fernando A. Morales

    (Universidad Nacional de Colombia, Sede Medellín)

  • Jairo A. Martínez

    (Universidad EAFIT)

Abstract

We introduce and asses several Divide-and-Conquer heuristic strategies, aimed at solving large instances of the 0–1 Minimization Knapsack Problem. The method subdivides a large problem in two smaller ones (or recursive iterations of the same procedure), in order to lower down the global computational complexity of the original problem, at the expense of a moderate loss of quality in the solution. Theoretical mathematical results are presented to assure a successful algorithmic application of the method and to suggest the potential strategies for its implementation. In contrast, due to the lack of theoretical results, the solution’s quality deterioration is measured empirically by means of Monte Carlo simulations for several types and values of the chosen strategies. Finally, introducing parameters of efficiency we suggest the best strategies depending on the data input.

Suggested Citation

  • Fernando A. Morales & Jairo A. Martínez, 2020. "Analysis of Divide-and-Conquer strategies for the 0–1 minimization knapsack problem," Journal of Combinatorial Optimization, Springer, vol. 40(1), pages 234-278, July.
    • Handle: RePEc:spr:jcomop:v:40:y:2020:i:1:d:10.1007_s10878-020-00584-2
    DOI: 10.1007/s10878-020-00584-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-020-00584-2
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-020-00584-2?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. Juan, Angel A. & Faulin, Javier & Grasman, Scott E. & Rabe, Markus & Figueira, Gonçalo, 2015. "A review of simheuristics: Extending metaheuristics to deal with stochastic combinatorial optimization problems," Operations Research Perspectives, Elsevier, vol. 2(C), pages 62-72.
    Full references (including those not matched with items on IDEAS)

    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. Noordhoek, Marije & Dullaert, Wout & Lai, David S.W. & de Leeuw, Sander, 2018. "A simulation–optimization approach for a service-constrained multi-echelon distribution network," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 114(C), pages 292-311.
    2. Romauch, Martin & Hartl, Richard F., 2017. "Capacity planning for cluster tools in the semiconductor industry," International Journal of Production Economics, Elsevier, vol. 194(C), pages 167-180.
    3. José García & Victor Yepes & José V. Martí, 2020. "A Hybrid k-Means Cuckoo Search Algorithm Applied to the Counterfort Retaining Walls Problem," Mathematics, MDPI, vol. 8(4), pages 1-22, April.
    4. Mohammad Peyman & Pedro J. Copado & Rafael D. Tordecilla & Leandro do C. Martins & Fatos Xhafa & Angel A. Juan, 2021. "Edge Computing and IoT Analytics for Agile Optimization in Intelligent Transportation Systems," Energies, MDPI, vol. 14(19), pages 1-26, October.
    5. Andrés Martínez-Reyes & Carlos L. Quintero-Araújo & Elyn L. Solano-Charris, 2021. "Supplying Personal Protective Equipment to Intensive Care Units during the COVID-19 Outbreak in Colombia. A Simheuristic Approach Based on the Location-Routing Problem," Sustainability, MDPI, vol. 13(14), pages 1-16, July.
    6. Manuel Chica & Joaquín Bautista & Jesica de Armas, 2019. "Benefits of robust multiobjective optimization for flexible automotive assembly line balancing," Flexible Services and Manufacturing Journal, Springer, vol. 31(1), pages 75-103, March.
    7. José García & José V. Martí & Víctor Yepes, 2020. "The Buttressed Walls Problem: An Application of a Hybrid Clustering Particle Swarm Optimization Algorithm," Mathematics, MDPI, vol. 8(6), pages 1-22, May.
    8. Omer Ozkan & Sezgin Kilic, 2023. "UAV routing by simulation-based optimization approaches for forest fire risk mitigation," Annals of Operations Research, Springer, vol. 320(2), pages 937-973, January.
    9. José García & Paola Moraga & Matias Valenzuela & Hernan Pinto, 2020. "A db-Scan Hybrid Algorithm: An Application to the Multidimensional Knapsack Problem," Mathematics, MDPI, vol. 8(4), pages 1-22, April.
    10. José Lemus-Romani & Marcelo Becerra-Rozas & Broderick Crawford & Ricardo Soto & Felipe Cisternas-Caneo & Emanuel Vega & Mauricio Castillo & Diego Tapia & Gino Astorga & Wenceslao Palma & Carlos Castro, 2021. "A Novel Learning-Based Binarization Scheme Selector for Swarm Algorithms Solving Combinatorial Problems," Mathematics, MDPI, vol. 9(22), pages 1-41, November.
    11. Diglio, Antonio & Peiró, Juanjo & Piccolo, Carmela & Saldanha-da-Gama, Francisco, 2021. "Solutions for districting problems with chance-constrained balancing requirements," Omega, Elsevier, vol. 103(C).
    12. David Schmaranzer & Roland Braune & Karl F. Doerner, 2021. "Multi-objective simulation optimization for complex urban mass rapid transit systems," Annals of Operations Research, Springer, vol. 305(1), pages 449-486, October.
    13. Rabbani, M. & Heidari, R. & Yazdanparast, R., 2019. "A stochastic multi-period industrial hazardous waste location-routing problem: Integrating NSGA-II and Monte Carlo simulation," European Journal of Operational Research, Elsevier, vol. 272(3), pages 945-961.
    14. Lehner, Roland, 2023. "Cross-Supply Chain Collaboration Platform for Pallet Management," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 138753, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    15. Martin Masek & Chiou Peng Lam & Luke Kelly & Martin Wong, 2023. "Discovering optimal strategy in tactical combat scenarios through the evolution of behaviour trees," Annals of Operations Research, Springer, vol. 320(2), pages 901-936, January.
    16. Louis Anthony Cox, 2020. "Answerable and Unanswerable Questions in Risk Analysis with Open‐World Novelty," Risk Analysis, John Wiley & Sons, vol. 40(S1), pages 2144-2177, November.
    17. Mohamed Hussein & Abdelrahman E. E. Eltoukhy & Amos Darko & Amr Eltawil, 2021. "Simulation-Optimization for the Planning of Off-Site Construction Projects: A Comparative Study of Recent Swarm Intelligence Metaheuristics," Sustainability, MDPI, vol. 13(24), pages 1-41, December.
    18. Yagmur S. Gök & Silvia Padrón & Maurizio Tomasella & Daniel Guimarans & Cemalettin Ozturk, 2023. "Constraint-based robust planning and scheduling of airport apron operations through simheuristics," Annals of Operations Research, Springer, vol. 320(2), pages 795-830, January.
    19. Ruddy Guerrero & Adrian Serrano-Hernandez & Jose Pascual & Javier Faulin, 2022. "Simulation Model for Wire Harness Design in the Car Production Line Optimization Using the SimPy Library," Sustainability, MDPI, vol. 14(12), pages 1-19, June.
    20. Bayliss, Christopher & Currie, Christine S.M. & Bennell, Julia A. & Martinez-Sykora, Antonio, 2019. "Dynamic pricing for vehicle ferries: Using packing and simulation to optimize revenues," European Journal of Operational Research, Elsevier, vol. 273(1), pages 288-304.

    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:spr:jcomop:v:40:y:2020:i:1:d:10.1007_s10878-020-00584-2. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.