Sensitivity analysis of the setup knapsack problem to perturbation of arbitrary profits or weights
Résumé
The setup knapsack problem can be viewed as a more complex version of the well-known classical knapsack problem. An instance of such a problem may be defined by a set N of n items that is divided into m different classes Fi,1im. For each class, only one item is considered as a setup item. The aim of the problem is to pack a subset of items in a knapsack of a predefined capacity that maximizes an objective function. In this paper, we analyze the sensitivity of an optimal solution depending on the variation of the profits or weights of arbitrary items. The optimality of the solution at hand is guaranteed by establishing the sensitivity interval that is characterized by both lower and upper values (called limits). First, two cases are distinguished when varying the profits: perturbation of the profit of an item (either ordinary or setup item) and, variation of the profits of a couple of items containing both setup and ordinary items belonging to the same class. Second, two cases are studied, where the perturbation concerns the weights: the variation is relied on the weight of an item and, the case of the variation of the weights of a subset of items. The established results are first illustrated throughout a didactic example, where both approximate and exact methods are used for analyzing the quality of the proposed results. Finally, an extended experimental part is proposed in order to evaluate the effectiveness of the proposed limits.