Binary salp swarm algorithm for discounted {0-1} knapsack problem

Binh Thanh Dang and Tung Khac Truong

PLOS ONE, 2022, vol. 17, issue 4, 1-28

Abstract: While the classical knapsack problem has been the object to be solved by optimization algorithm proposals for many years, another version of this problem, discounted {0-1} knapsack problem, is gaining a lot of attention recently. The original knapsack problem requires selecting specific items from an item set to maximize the total benefit while ensuring that the total weight does not exceed the knapsack capacity. Meanwhile, discounted {0-1} knapsack problem has more stringent requirements in which items are divided into groups, and only up to one item from a particular group can be selected. This constraint, which does not exist in the original knapsack problem, makes discounted {0-1} knapsack problem even more challenging. In this paper, we propose a new algorithm based on salp swarm algorithm in the form of four different variants to resolve the discounted {0-1} knapsack problem. In addition, we also make use of an effective data modeling mechanism and a greedy repair operator that helps overcome local optima when finding the global optimal solution. Experimental and statistical results show that our algorithm is superior to currently available algorithms in terms of solution quality, convergence, and other statistical criteria.

Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0266537 (text/html)
https://journals.plos.org/plosone/article/file?id= ... 66537&type=printable (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:plo:pone00:0266537

DOI: 10.1371/journal.pone.0266537

Access Statistics for this article

More articles in PLOS ONE from Public Library of Science
Bibliographic data for series maintained by plosone ().