Sensitivity of the optimum to perturbations of the weight or profit of an item in the binary knapsack problem

Mhand Hifi*, LaRIA et CERMSEM
Hedi Mhalla*, LaRIA et CERMSEM
Slim Sadfi*, LaRIA et CERMSEM

Résumé. Dans le présent article nous étudions l'adaptabilité du problème de knapsack Unidimensionnel, noté 0 - 1KP, à variables binaires. L'étude de l'adaptabilité se repose sur la notion de la variation (ou perturbation) : (i) d'un profit de la fonction objective et/ou (ii) d'un poids de la contrainte du knapsack. La première partie est consacrée à l'étude de la sensibilité de l'optimum par rapport à une variation du profit et dans une deuxième partie, nous traitons la sensibilité de l'optimum par rapport à une variation du poids. Dans les deux cas, nous cherchons les intervalles de limites dans lesquelles le profit (resp. le poids) peut varier sans que la solution optimale change, tout en tirant profit de la solution optimale du problème 0 -1KP. Finalement, nous proposons (à la fin de chaque partie) un algorithme polynomial qui permet la recherche des limites de sensibilité de l'optimum.
Mots clés : Sac à dos, analyse de sensibilité, optimisation combinatoire, programmation dynamique.

Abstract. In the binary single constraint Knapsack Problem, noted 0-1KP, we are given a knapsack of fixed capacity c and a set of n items. Each item j, j = 1,...,n, has an associated size or weight w_j and a profit p_j. The goal is to determine whether or not item j, j = 1,...,n should be included in the knapsack. The objective is to maximize the total profit without exceeding the capacity c of the knapsack. In this paper, we study the sensitivity of the optimum of the 0 - 1KP, to perturbations of either the profit or the weight of a single item.
Keywords : Combinatorial optimization, knapsack problem, optimality, sensitivity analysis.

JEL Classification : C44, C61, C63.

*LaRIA, Laboratoire de Recherche en Informatique d'Amiens, 5 rue du Moulin Neuf, 80000 Amiens.