Skip to Main content Skip to Navigation
Conference papers

A new Hybrid Heuristic for the 0-1 Knapsack Sharing Problem

Abstract : In this paper we consider the 0-1 knapsack sharing problem, which is a max-min optimization problem with a knapsack constraint. This problem has a wide range of commercial applications and occurs when resources have to be shared or distributed fairly to several entities. We propose a new hybrid heuristic combining an iterative linear programming-based algorithm with a quantum particle swarm optimization. The iterative linear programming-based algorithm generates two sequences of upper and lower bounds, respectively, around the optimal value of the problem, in order to decrease the gap between the bounds and to converge to an optimal solution of the problem. To improve the efficiency of the approach we integrate local search techniques. In particular, we consider the quantum particle swarm optimization to enhance the solutions visited by the iterative method. The computational results show that the proposed approach can produce optimal or near-optimal solutions in a short and reasonable amount of running time.
Document type :
Conference papers
Complete list of metadata
Contributor : Kathleen Torck Connect in order to contact the contributor
Submitted on : Thursday, December 9, 2021 - 4:22:07 PM
Last modification on : Friday, December 10, 2021 - 3:54:10 AM


  • HAL Id : hal-03472998, version 1



Boukthir Haddar, Mahdi Khemakhem, Said Hanafi, Christophe Wilbaut, Habib Chabchoub. A new Hybrid Heuristic for the 0-1 Knapsack Sharing Problem. International Conference on Industrial Engineering and Systems Management (IEEE IESM 2013), Oct 2013, Rabat, Morocco. ⟨hal-03472998⟩



Les métriques sont temporairement indisponibles