Title: A two-stage hybrid method for the multi-scenarios max-min knapsack problem

Authors: Thekra Aldouri; Mhand Hifi

Addresses: Université de Picardie Jules Verne, EPROAD – EA 4669, 7 rue du Moulin Neuf, 80000 Amiens, France ' Université de Picardie Jules Verne, EPROAD – EA 4669, 7 rue du Moulin Neuf, 80000 Amiens, France

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.

Keywords: heuristic; combinatorial; knapsack; optimisation.

DOI: 10.1504/IJIEI.2018.091011

International Journal of Intelligent Engineering Informatics, 2018 Vol.6 No.1/2, pp.99 - 114

Received: 18 Nov 2016
Accepted: 20 Jun 2017
Published online: 06 Apr 2018 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article