Performance Analysis of Simulated Annealing on the 0-1 Knapsack Problem

This study addresses the 0-1 Knapsack Problem (KP), a classic variant of knapsack problems, using the Simulated Annealing (SA) algorithm. The 0-1 KP, an NP-hard problem, involves selecting items with given weights and values to maximize total value without exceeding a capacity of knapsack. SA's analogy to the annealing process of metals allows it to efficiently explore the solution space by probabilistically accepting suboptimal solutions at higher temperatures, thus avoiding local optima. The paper evaluates the performance of SA through extensive computational experiments on various problem instances. Results indicate that while SA achieves optimal or near-optimal solutions for smaller instances, its performance decreases for larger instances, highlighting a trade-off between solution quality and problem size. The study suggests multiple runs to achieve consistent results and proposes potential future enhancements, including hybrid methods and improved cooling schedules, to boost SA's efficiency for larger, more complex scenarios.