Skip to Main content Skip to Navigation
Journal articles

A hybrid heuristic for the 0–1 Knapsack Sharing Problem

Abstract : The Knapsack Sharing Problem (KSP) is a variant of the well-known NP-hard knapsack problem that has received a lot of attention from the researches as it appears into several real-world problems such as allocating resources, reliability engineering, cloud computing, etc. In this paper, we propose a hybrid approach that combines an Iterative Linear Programming-based Heuristic (ILPH) and an improved Quantum Particle Swarm Optimization (QPSO) to solve the KSP. The ILPH is an algorithm conceived to solve 0–1 mixed integer programming. It solves a series of reduced problems generated by exploiting information obtained through a series of linear programming relaxations and tries to improve lower and upper bounds on the optimal value. We proposed several enhancements to strengthen the performance of the ILPH: (i) New valid constraints are introduced to speed up the resolution of reduced problems; (ii) A local search is incorporated as an intensification process to reduce the gap between the upper and the lower bounds. Finally, QPSO is launched by using the k best solutions encountered in the ILPH process as an initial population. The proposed QPSO explores feasible and infeasible solutions. Experimental results obtained on a set of problem instances of the literature and other new harder ones clearly demonstrate the good performance of the proposed hybrid approach in solving the KSP.
Document type :
Journal articles
Complete list of metadata

https://hal-uphf.archives-ouvertes.fr/hal-03401168
Contributor : Mylène Delrue Connect in order to contact the contributor
Submitted on : Monday, October 25, 2021 - 12:00:12 PM
Last modification on : Tuesday, October 26, 2021 - 4:00:32 AM

Identifiers

Collections

Citation

Boukthir Haddar, Mahdi Khemakhem, Said Hanafi, Christophe Wilbaut. A hybrid heuristic for the 0–1 Knapsack Sharing Problem. Expert Systems with Applications, Elsevier, 2015, 42 (10), pp.4653-4666. ⟨10.1016/j.eswa.2015.01.049⟩. ⟨hal-03401168⟩

Share

Metrics

Record views

6