Efficient algorithms for the knapsack sharing problem

Mhand Hifi*, CERMSEM et PRiSM
Slim Sadfi, CERMSEM
Abdelkader Sbihi, CERMSEM


Résumé. Dans cet article, nous proposons deux méthodes efficaces pour la résolution du problème de la distribution, équitable (Knapsack Sharing Problem, noté KSP). Une instance du KSP est définie par une capacité c et un ensemble de n objets, où à chaque objet j, j=1,...,n, associe un profit pj et un poids wj. L'ensemble des objets est divisé en m différentes classes et le but est de déterminer un sous-ensemble d'objets qui rentre dans le knapsack réalisant la valeur max-min sur l'ensemble des classes. La première méthode approchée est considérée comme une recherche locale simple, notée SDTS. Dans cette méthode nous utilisons un paramètre représentant la profondeur des éléments critiques des classes considérées tout en utilisant une liste tabou. La liste tabou nous permet d'éviter de retomber sur des solutions déjà visitées auparavant. La deuxième méthode approchée est une version plus sophistiquée. Cette fois, la trajectoire de la profondeur est utilisée sur deux différentes directions tout en maintenant la liste tabou déjà utilisée dans la première méthode. Les méthodes proposées ont été testées sur un ensemble d'instances de la littérature. Les résultats obtenus ont été très satisfaisants.

Abstract. In this paper, we propose two efficient algorithms in order to approximately solve the Knapsack Sharing Problem (KSP). In KSP, we have a knapsack of capicity c and a set of n objects, where each object j, j=1,...,n, is associated with a profit pj and a weight wj. The set of objects is divided into m different classes of objects and, the aim is to determine a subset of objects to be included in the knapsack which realizes a max-min value over all classes. The first algorithm is considered as a simple local search, namely Simple Depth Tabu Search (SDTS), in which a depth-parameter and a tabu list are used. The second algorithm, namely Multiple Depth Tabu Search (MDTS), is considered as an extended approach in which the depth-parameter is applied in two different ways. The proposed algorithms are implemented and computational experiments are carried out to analyze their behavior. Encouraging results have been obtained.
Keywords : Combinatorial optimization, heuristics, knapsack, local searches.

*PRiSM-CNRS URA 1525, Université de Versailles-Saint-Quentin en Yvelines, 45 avenue des Etats-Unis, 78035 Versailles Cedex, France