A two-stage hybrid method for the multi-scenarios max-min knapsack problem. (2018)

• Record Type: Journal Article
• Authors: Aldouri, Thekra; Hifi, Mhand
• Is Part Of: International journal of intelligent engineering informatics. Volume 6:Number 1/2(2018)
• Page Start: 99
• Page End: 114
• Publication Date: 2018
• Subjects: heuristic -- combinatorial -- knapsack -- optimisation; Artificial intelligence -- Engineering applications -- Periodicals; Engineering -- Computer programs -- Periodicals; Knowledge management -- Periodicals; 620.0028563
• Languages: English
• ISSNs: 1758-8715

Abstract

In this paper, we propose a two-stage hybrid method in order to solve approximately the multi-scenarios max-min knapsack problem. The proposed method is based upon three complementary stages: 1) the building stage; 2) the combination stage; 3) the two-stage rebuild stage. First, the building stage serves to provide a starting feasible solution by using a greedy procedure; each item is randomly chosen for reaching a starting population of solutions. Second, the combination stage tries to provide each new solution by combining subsets of (starting) solutions. Third, the rebuild stage tries to make intensification in order to improve the solutions at hand. The proposed method is evaluated on a set of benchmark instances taken from the literature. The obtained results are compared to those reached by the best algorithms available in the literature. The results show that the proposed method provides better solutions than those already published.