A new Hybrid Heuristic for the 0-1 Knapsack Sharing Problem
Résumé
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.