An iterative rounding strategy-based algorithm for the set-union knapsack problem
Résumé
The knapsack problem arises in several real-world applications, like manufacturing systems, transportation, cutting and packing, and hydrological studies. In this paper, we investigate the use of an iterative rounding strategy-based algorithm for tackling a special knapsack problem: the set-union knapsack problem. First, the approach builds a series of starting partial solutions by using the principle of fractional values related to a series of linear relaxations of the (sub)instance at hand. Second, each step of the rounding procedure is coupled with an enhanced local search procedure, where its goal is to search around a local partial solution by applying the so-called critical element tailored for the problem studied. Third, both degrading and re-optimization strategies are introduced in order to extend the diversified search space. Finally, all strategies are embedded into an iterative search in order to augmenting the quality of the solutions. The performance of the proposed method is evaluated on benchmark instances of the literature and new large-scale instances; its provided results are compared to those reached by the Cplex solver and the best methods available in the literature. The method seems competitive, where it is able to achieve new (lower) bounds and matches the rest of the bounds.