IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v10y2022i17p3183-d905812.html
   My bibliography  Save this article

Binarization Technique Comparisons of Swarm Intelligence Algorithm: An Application to the Multi-Demand Multidimensional Knapsack Problem

Author

Listed:
  • José García

    (Escuela de Ingeniería de Construcción y Transporte, Pontificia Universidad Católica de Valparaíso, Valparaíso 2362804, Chile)

  • Paola Moraga

    (Escuela de Ingeniería de Construcción y Transporte, Pontificia Universidad Católica de Valparaíso, Valparaíso 2362804, Chile)

  • Broderick Crawford

    (Escuela de Ingeniería Informática, Pontificia Universidad Católica de Valparaíso, Avenida Brasil 2241, Valparaíso 2362807, Chile)

  • Ricardo Soto

    (Escuela de Ingeniería Informática, Pontificia Universidad Católica de Valparaíso, Avenida Brasil 2241, Valparaíso 2362807, Chile)

  • Hernan Pinto

    (Escuela de Ingeniería de Construcción y Transporte, Pontificia Universidad Católica de Valparaíso, Valparaíso 2362804, Chile)

Abstract

In order to minimize execution times, improve the quality of solutions, and address more extensive target situations, optimization techniques, particularly metaheuristics, are continually improved. Hybridizing procedures are one of these noteworthy strategies due to their wide range of applications. This article describes a hybrid algorithm that combines the k-means method to produce a binary version of the cuckoo search and sine cosine algorithms. The binary algorithms are applied on the NP -hard multi-demand multidimensional knapsack problem. This problem is of particular interest because it has two types of constraints. The first group of constraints is related to the capacity of the knapsacks, and a second type is associated with the demand that must be met. Experiments were undertaken to acquire insight into the contribution of the k-means technique and the local search operator to the final results. Additionally, a comparison is made with two other types of binarization, the first based on a random method and the second based on the percentile concept. The results reveal that the k-means hybrid algorithm consistently provides superior results in most cases studied. In particular, incorporating the local search operator improved the results by an average of 0.23%. On the other hand, when comparing the results with 100 items and 30-30 restrictions, k-means was 1.06% better on average than the random operator.

Suggested Citation

  • José García & Paola Moraga & Broderick Crawford & Ricardo Soto & Hernan Pinto, 2022. "Binarization Technique Comparisons of Swarm Intelligence Algorithm: An Application to the Multi-Demand Multidimensional Knapsack Problem," Mathematics, MDPI, vol. 10(17), pages 1-20, September.
    • Handle: RePEc:gam:jmathe:v:10:y:2022:i:17:p:3183-:d:905812
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/10/17/3183/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/10/17/3183/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. 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.
    2. 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.
    3. José García & Gino Astorga & Víctor Yepes, 2021. "An Analysis of a KNN Perturbation Operator: An Application to the Binarization of Continuous Metaheuristics," Mathematics, MDPI, vol. 9(3), pages 1-20, January.
    4. Broderick Crawford & Ricardo Soto & Gino Astorga & José García & Carlos Castro & Fernando Paredes, 2017. "Putting Continuous Metaheuristics to Work in Binary Search Spaces," Complexity, Hindawi, vol. 2017, pages 1-19, May.
    5. George J. Beaujon & Samuel P. Marin & Gary C. McDonald, 2001. "Balancing and optimizing a portfolio of R&D projects," Naval Research Logistics (NRL), John Wiley & Sons, vol. 48(1), pages 18-40, February.
    6. 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.
    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. Marcelo Becerra-Rozas & José Lemus-Romani & Felipe Cisternas-Caneo & Broderick Crawford & Ricardo Soto & Gino Astorga & Carlos Castro & José García, 2022. "Continuous Metaheuristics for Binary Optimization Problems: An Updated Systematic Literature Review," Mathematics, MDPI, vol. 11(1), pages 1-32, December.
    2. 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).
    3. José García & José Lemus-Romani & Francisco Altimiras & Broderick Crawford & Ricardo Soto & Marcelo Becerra-Rozas & Paola Moraga & Alex Paz Becerra & Alvaro Peña Fritz & Jose-Miguel Rubio & Gino Astor, 2021. "A Binary Machine Learning Cuckoo Search Algorithm Improved by a Local Search Operator for the Set-Union Knapsack Problem," Mathematics, MDPI, vol. 9(20), pages 1-19, October.
    4. 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.
    5. Michael J. Ryoba & Shaojian Qu & Yongyi Zhou, 2021. "Feature subset selection for predicting the success of crowdfunding project campaigns," Electronic Markets, Springer;IIM University of St. Gallen, vol. 31(3), pages 671-684, September.
    6. 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.
    7. Li, Mingjie & Hao, Jin-Kao & Wu, Qinghua, 2024. "A flow based formulation and a reinforcement learning based strategic oscillation for cross-dock door assignment," European Journal of Operational Research, Elsevier, vol. 312(2), pages 473-492.
    8. 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.
    9. Hongbo Li & Rui Chen & Xianchao Zhang, 2022. "Uncertain Public R&D Project Portfolio Selection Considering Sectoral Balancing and Project Failure," Sustainability, MDPI, vol. 14(23), pages 1-13, November.
    10. 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.
    11. Paulo Figueroa-Torrez & Orlando Durán & Broderick Crawford & Felipe Cisternas-Caneo, 2023. "A Binary Black Widow Optimization Algorithm for Addressing the Cell Formation Problem Involving Alternative Routes and Machine Reliability," Mathematics, MDPI, vol. 11(16), pages 1-23, August.
    12. Zhang, Jian & Dridi, Mahjoub & El Moudni, Abdellah, 2020. "Column-generation-based heuristic approaches to stochastic surgery scheduling with downstream capacity constraints," International Journal of Production Economics, Elsevier, vol. 229(C).
    13. 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.
    14. Sergio Valdivia & Ricardo Soto & Broderick Crawford & Nicolás Caselli & Fernando Paredes & Carlos Castro & Rodrigo Olivares, 2020. "Clustering-Based Binarization Methods Applied to the Crow Search Algorithm for 0/1 Combinatorial Problems," Mathematics, MDPI, vol. 8(7), pages 1-42, July.
    15. Dalton Garcia Borges de Souza & Erivelton Antonio dos Santos & Nei Yoshihiro Soma & Carlos Eduardo Sanches da Silva, 2021. "MCDM-Based R&D Project Selection: A Systematic Literature Review," Sustainability, MDPI, vol. 13(21), pages 1-34, October.
    16. Çağlar, Musa & Gürel, Sinan, 2019. "Impact assessment based sectoral balancing in public R&D project portfolio selection," Socio-Economic Planning Sciences, Elsevier, vol. 66(C), pages 68-81.
    17. Michael J. Ryoba & Shaojian Qu & Ying Ji & Deqiang Qu, 2020. "The Right Time for Crowd Communication during Campaigns for Sustainable Success of Crowdfunding: Evidence from Kickstarter Platform," Sustainability, MDPI, vol. 12(18), pages 1-22, September.
    18. 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.
    19. Marcelo Becerra-Rozas & José Lemus-Romani & Felipe Cisternas-Caneo & Broderick Crawford & Ricardo Soto & José García, 2022. "Swarm-Inspired Computing to Solve Binary Optimization Problems: A Backward Q-Learning Binarization Scheme Selector," Mathematics, MDPI, vol. 10(24), pages 1-30, December.
    20. Mauricio Castillo & Ricardo Soto & Broderick Crawford & Carlos Castro & Rodrigo Olivares, 2021. "A Knowledge-Based Hybrid Approach on Particle Swarm Optimization Using Hidden Markov Models," Mathematics, MDPI, vol. 9(12), pages 1-21, June.

    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:gam:jmathe:v:10:y:2022:i:17:p:3183-:d:905812. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.