The depth and width of local minima in discrete solution spaces

Heuristic search techniques such as simulated annealing and tabu search require ‘tuning’ of parameters (i.e., the cooling schedule in simulated annealing, and the tabu list length in tabu search), to achieve optimum performance. In order for a user to anticipate the best choice of parameters, thus avoiding extensive experimentation, a better understanding of the solution space of the problem to be solved is needed. Two functions of the solution space, the maximum depth and the maximum width of local minima are discussed here, and sharp bounds on the value of these functions are given for the 0-1 knapsack problem and the cardinality set covering problem.