Tolerance analysis of knapsack problems – Københavns Universitet

Tolerance analysis of knapsack problems

Tolerance analysis, or post-optimal analysis, is the task of understanding the behavior of the solution of a problem due to changes in the data. Frequently, tolerance analysis is as important as obtaining the optimal solution itself.

Post-optimal analysis for linear programming problems is well established and widely used. However, for integer programming problems the task is much more computationally demanding, and various approaches based on branch-and-bound or cutting planes have been presented.

In the present paper we show how to perform exact post-optimal analysis for the 0-1 knapsack problem in amortized time $O(c \log n)$ for each item, where $n$ is the number of items, and $c$ is the capacity of the knapsack. Moreover, we show how various bounds can be used to determine approximate tolerance limits in time $O(\log n)$ or $O(1)$ using the Dantzig bound and Dembo-Hammer bound respectively. The running times and quality of the tolerance limits of all exact and approximate algorithms are experimentally compared, showing that all tolerance limits can be found in fractions of a second (per item). The approximate bounds are of good quality for large-sized instances, while it is worth using the exact approach for smaller instances.

Joint work with: Alima Saidi