Sensitivity analysis of a greedy heuristic for knapsack problems

Sensitivity analysis of a greedy heuristic for knapsack problems

0.00 Avg rating0 Votes
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: , ,
Keywords: heuristics, optimization
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.