Sensitivity analysis of the knapsack sharing problem : perturbation of the profit

URL des Documents de travail :http://mse.univ-paris1.fr/CES2007/2007064B.pdfDocuments de travail du Centre d'Economie de la Sorbonne 2007.64 - ISSN : 1955-611XIn this paper, we study the sensitivity of the optimum of a max-min combinatorial optimization problem, namely the Knapsack Sharing Problem (KSP), to the perturbation of the profit of an arbitrary item. We mainly establish the interval limits of each perturbed item by applying a reduction of the original problem into a series of single knapsack problems. We propose a solution procedure in order to establish these interval limits. The principle of the method is to stabilize the optimal solution in the perturbed problem, following two cases : (i) when the item belongs to an optimal class, and (ii) when the item belongs to a non optimal class. We also consider either the problem admits a unique or multiple optimal classes. Finally, we evaluate the effectiveness of the proposed solution procedure on several problem instances of the literature.Dans cet article, nous étudions la sensibilité de l'optimum d'un problème d'optimisation combinatoire de max-min, à savoir le problème du partage équitable, noté KSP (en anglais Knapsack Sharing Problem), soumis à la perturbation du profit d'un élément quelconque. Nous établissons principalement les limites de l'intervalle de sensibilité pour chaque profit en utilisant la réduction du problème initial en une série de problèmes de sac à dos. Nous proposons un algorithme permettant le calcul de ces limites en temps polynomial. On distingue plusieurs cas suivant que l'élément perturbé appartient ou pas à une classe optimale et suivant que l'instance du problème admet une unique ou plusieurs classes optimales. Enfin, nous évaluons l'efficacité des intervalles obtenus par cette procédure sur plusieurs instances de la littérature