Article ID: | iaor20063640 |
Country: | Netherlands |
Volume: | 169 |
Issue: | 1 |
Start Page Number: | 340 |
End Page Number: | 350 |
Publication Date: | Feb 2006 |
Journal: | European Journal of Operational Research |
Authors: | Chakravarti Nilotpal, Sierksma Gerard, Ghosh Diptesh |
Keywords: | heuristics, optimization |
In this paper, we carry out parametric analysis as well as a tolerance limit based sensitivity analysis of a greedy heuristic for two knapsack problems – the 0–1 knapsack problem and the subset sum problem. We carry out the parametric analysis based on all problem parameters. In the tolerance limit based approach, we use a definition of the sensitivity analysis problem that is polynomial for polynomial heuristics. One of the interesting and counterintuitive results described in this paper is that the tolerance limits obtained from the heuristic sensitivity analysis cannot be used as bounds for the tolerance limits of the sensitivity analysis of optimal solutions in most cases.