A Rough Sets based modified Scatter Search algorithm for solving 0-1 Knapsack problem

Abstract

This paper presents a new search methodology for different sizes of 0-1 Knapsack Problem (KP). The proposed methodology uses a modified scatter search as a meta-heuristic algorithm. Moreover, rough set theory is implemented to improve the initial features of scatter search. Thereby, the preliminary results of applying the proposed approach on some benchmark dataset appear that the proposed method was capable of providing better results in terms of time and quality of solutions.

Keywords

• Discrete optimization
• 0-1 Knapsack problem
• Rough sets theory
• Scatter search algorithm