Arrêt de service programmé du vendredi 10 juin 16h jusqu’au lundi 13 juin 9h. Pour en savoir plus
Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

Effect of the local branching strategy on the descent method: The case of the generalized multiple knapsack with setup

Abstract : In this paper, we investigate the use of the local branching strategy into an iterative descent method for tackling the generalized multiple knapsack problem with setup. An instance of the problem is composed of a set of classes containing items, and a set of available knapsacks. Its objective consists in selecting the subsets of items belonging to the classes with a maximum objective value: each item is characterized with its profit and weight while a class is characterized with its cost such that a given item may be selected whenever its corresponding class is activated, and an item can be configured (setup) for a single knapsack. The proposed iterative method starts by solving a series of reduced subproblems built by adding a series of cardinality constraints. Next, the local branching strategy is iteratively employed for highlighting the efficiency of the method. Finally, the behavior of the method is evaluated on a set of instances extracted from the literature, where its achieved bounds are compared to those reached by the best methods available in the literature. A statistical analysis is also provided showing the high performance of the method. New bounds are discovered.
Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal-u-picardie.archives-ouvertes.fr/hal-03566153
Contributeur : Louise Dessaivre Connectez-vous pour contacter le contributeur
Soumis le : vendredi 11 février 2022 - 13:45:55
Dernière modification le : samedi 12 février 2022 - 03:00:17

Identifiants

Collections

Citation

Samah Boukhari, Isma Dahmani, Mhand Hifi. Effect of the local branching strategy on the descent method: The case of the generalized multiple knapsack with setup. Computers & Industrial Engineering, 2022, 165, ⟨10.1016/j.cie.2022.107934⟩. ⟨hal-03566153⟩

Partager

Métriques

Consultations de la notice

14