A hybrid heuristic for the 0–1 Knapsack Sharing Problem

Overview & Synopsis

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.