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

Samah Boukhari , Isma Dahmani , Mhand Hifi (1)

1 EPROAD - Eco-Procédés Optimisation et Aide à la Décision - UR UPJV 4669

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.

Domaines: Informatique [cs]

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⟩