Stochastic Local Search combined with Simulated Annealing for the 0-1 Multidimensional Knapsack Problem

The 0-1 Multidimensional Knapsack Problem (MKP) is a widely-studied problem in combinatorial optimization domaine which has been proven as NP-hard. Various approximate heuristics have been developed and applied effectively to this problem, such as local search and evolutionary methods. This paper proposes the Stochastic Local Search-Simulated Annealing (SLSA) approach that combines the stochastic local search (SLS) and the simulated annealing (SA) to solve the MKP. Three main techniques are introduced in SLSA which are: the neighborhood creation, the solution reparation and the mutation strategy. We validate the effectiveness of the proposed approach through an experimental study performed on several benchmark problems commonly used in the literature. The obtained results show that the SLS and SA, when combined appropriately can provide better results than either SLS or SA alone.