The knapsack sharing problem : an exact algorithm

Mhand Hifi*, CERMSEM et PRiSM
Slim Sadfi**, LRI

Résumé. Dans cet article, nous proposons un nouvel algorithme optimal pour le problème de la distribution équitable. Cet algorithme paraît très performant dans le sens où l'on arrive à résoudre des instances de taille importante en un temps d'exécution très faible. Le problème de la distribution équitable est décomposé sous forme d'une série de problèmes de knapsack unidimensionnels. La résolution du problème est réalisée par l'application de la programmation dynamique combinée avec une stratégie par "le meilleur d'abord". La performance de l'algorithme est évaluée sur un nombre d'instances (240 instances). Par ailleurs, nous avons montré que l'algorithme est parallélisable en utilisant un algorithme en "pipeline".
Mots clés : Optimisation combinatoire, problème de la distribution équitable, algorithmes séquentiels.

Abstract. In this paper, we propose an optimal algorithm for the knapsack sharing problem. The proposed algorithm seems quite efficient in the sense that it solves quickly some large problem instances. The problem is decomposed on a series of single constraint knapsack problems and by applying the dynamique programming and another strategy, we solve optimally the original problem. The performance of the exact algorithm is evaluated on a set of medium and large problem instances (a total of 240 problem instances). This algorithm is parallelizable and this is one of its important feature.
Keywords : Combinatorial optimization, knapsack sharing, dynamic programming, sequential algorithms.

*PRiSM, URA 1525, CNRS, Université de Versailles Saint-Quentin-en-Yvelines, 45 Avenue des Etats-Unis, 78035 Versailles Cedex.
**LRI, URA 410, CNRS, Université de Paris XI, Centre d'Orsay, 91405 Orsay.