Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

An iterative rounding strategy-based algorithm for the set-union knapsack problem

Abstract : 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.
Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal-u-picardie.archives-ouvertes.fr/hal-03617881
Contributeur : Louise Dessaivre Connectez-vous pour contacter le contributeur
Soumis le : mercredi 23 mars 2022 - 18:08:02
Dernière modification le : jeudi 24 mars 2022 - 03:00:22

Identifiants

Collections

Citation

Isma Dahmani, Meriem Ferroum, Mhand Hifi. An iterative rounding strategy-based algorithm for the set-union knapsack problem. Soft Computing, 2021, 25 (21), pp.13617-13639. ⟨10.1007/s00500-021-06091-8⟩. ⟨hal-03617881⟩

Partager

Métriques

Consultations de la notice

4