Sensitivity analysis of the knapsack problem: Tighter lower and upper bound limits

Abstract

In this paper, we study the sensitivity of the optimum of the knapsack problem to the perturbation of the profit of a subset of items. We propose a polynomial heuristic in order to establish both lower and upper bound limits of the sensitivity interval. The aim is to stabilize any given optimal solution obtained by applying any exact algorithm. We then evaluate the effectiveness of the proposed solution procedure on an example and a set of randomly generated problem instances.

Keywords

Combinatorial optimization / knapsack / sensitivity analysis

References

[1] Belgacem, T. & Hifi, M. (2006). Analyse de la sensibilité de l’optimum pour le problème du knapsack: perturbation de plusieurs profits. 7-ième Congrés de la ROADEF, Lille, France

[2] Belgacem, T. & Hifi, M. (2007). Sensitivity analysis of the optimum to perturbation of the profit of a subset of items in the binary knapsack problem. Working Paper, CES, Equipe CERMSEM, Université Paris 1, France

[3] Belgacem T., Hifi M.. Sensitivity analysis of the knapsack sharing problem: perturbation of the weight of an item. Computers and Operations Research, 2008, 35: 295-308.

[4] Blair C.. Sensitivity analysis of knapsack problems: a negative result. Discrete Applied Mathematics, 1998, 81: 133-139.

[5] Dantzig G.B.. Discrete variable extremum problems. Operations Research, 1957, 5: 266-277.

[6] Ghosh D., Charkravarti D., Sierksma G.. Sensitivity analysis of a greedy heuristic for knapsack problems. European Journal of Operational Research, 2006, 169: 340-350.

[7] Gilmore P.C., Gomory R.E.. The theory and computation of knapsack functions. Operations Research, 1966, 13: 879-919.

[8] Greenberg, H.J. (1998). An annotated bibliography for post-solution analysis in mixed integer programming and combinatorial optimization. In: Woodruff D.L. (eds.), Advances in Computational and Stochastic Optimization, Logic Programming, and Heuristic Search, pp. 97–148. Kluwer Academic Publishers

[9] Hifi M., Mhalla H., Sadfi S.. Sensitivity of the optimum to perturbations of the profit or weight of an item in the binary knapsack problem. Journal of Combinatorial Optimization, 2005, 10: 239-260.

[10] Hifi, M., Mhalla, H. & Sadfi, S. (2004). Adaptive algorithms for the knapsack problem: perturbation of an arbitrary item. Working Paper, CERMSEM-CNRS UMR 8095, MSE, Université Paris 1

[11] Kellerer H., Pferschy U., Pisinger D.. Knapsack Problems, 2004, Berlin: Springer Verlag.

[12] Martello S., Toth P.. An upper bound for the zero-one knapsack problem and a branch and bound algorithm. European Journal of Operational Research, 1977, 1: 169-175.

[13] Nauss R.. Parametric Integer Programming, 1979, Columbia, Missouri: University of Missouri Press.

[14] Pisinger D.. Core problems in knapsack algorithms. Operations Research, 1999, 47: 570-575.

[15] Woeginger G.J.. Sensitivity analysis for knapsack problems: another negative result. Discrete Applied Mathematics, 1999, 92: 247-251.