The Genetic Edge: Revolutionizing Multi-Constraint Fractional Knapsack Solutions

Apurva Tiwari () and Mahesh Kumar Tiwari ()

SPAST Reports, 2024, vol. 1, issue 8

Abstract: Under linear constraints, a greedy algorithm effectively solves the fractional knapsack problem. However, when additional constraints, such as weight and risk, are added, the complexity of the approach rises. Previous studies have shown that the greedy strategy is optimal under single linear constraints and have provided comprehensive documentation of its efficacy in solving the fractional knapsack problem in straightforward, unconstrained circumstances. Nevertheless, there hasn't been much research done on using greedy algorithms to solve issues with many constraints. This study examines how well genetic algorithms (GAs) perform in comparison to the greedy technique for solving the fractional knapsack problem under conditions with various restrictions. Our results show that, although the greedy method is still efficient in linear or unconstrained circumstances, GAs perform better when dealing with various constraints and provide better solutions in spite of their increased complexity of calculation. This study demonstrates the benefits of using evolutionary algorithms to solve difficult restricted optimization issues when more conventional approaches fall short.

Keywords: Knapsack Problem; Fractional knapsack; multiple constraints; Genetic Algorithm; Partition Method (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
https://spast.org/article/view/5111/455 (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:bps:jspath:v:1:y:2024:i:8:id:5111

Access Statistics for this article

SPAST Reports is currently edited by Srinesh Singh Thakur

More articles in SPAST Reports from SPAST Foundation
Bibliographic data for series maintained by Srinesh Singh Thakur ().