Comparison of Feasible Initial Solution Methods for the Knapsack Problem

Abstract

The Knapsack Problem (KP) is a combinatorial optimization challenge that involves selecting a subset of items with specific weights and values to maximize an objective without exceeding a weight limit. As an NP-hard problem, it has theoretical significance and real-world applications like resource allocation and project selection. Solving KP often relies on metaheuristic algorithms, which benefit from high-quality initial solutions generated using heuristic approaches such as greedy algorithms, random selection with feasibility checks, or hybrid strategies. However, generating feasible initial solutions becomes increasingly difficult in large-scale cases with numerous alternatives and budget constraints. This study systematically compares initial solution generation methods for KP under such constraints. Using a tailored dataset for project selection, we evaluate the convergence performance of the artificial bee colony algorithm with different initialization strategies. The study examines how initial solutions influence convergence rates and final results. Key findings show that the Random method works well for small datasets (10 projects) but struggles with larger ones, failing at 100+ projects. The Random with Feasibility Check method consistently produces near-optimal solutions. The Repair method ensures feasibility but increases computation time, while the MaxMin method offers greater efficiency with fewer iterations and reduced computation time. These insights are valuable for tackling large-scale, budget-constrained optimization problems. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2026.