Heuristic sensitivity analysis in a combinatoric environment: An exposition and case study

Sensitivity or post-optimality analysis investigates the effect of parametric changes on heuristic robustness and solution quality. This approach is relatively unexplored for combinatorial optimization problems, and yet is of considerable interest in analyzing performance characteristics of heuristic approaches. The purpose of this paper is to: (1) develop the semantics and rational of parametric analysis within the combinatoric environment; (2) present as an example the design and implementation of sensitivity analysis procedures for a newly developed heuristic – the Variable-Depth-Search Heuristic – to solve the Generalized Assignment Problem. The concepts and methodology discussed in this paper may as well be applied to other heuristics, or in developing a heuristic sensitivity analysis procedure for a large-scale optimization method.