Tabu thresholding: Improved search by nonmonotonic trajectories

There is an appeal to methods like simulated annealing and threshold acceptance that operate by imposing a monotonically declining ceiling on objective function levels or degrees of disimprovement (treated probabilistically or deterministically). An alternative framework, embodied in tabu search, instead advocates a nonmonotonic form of control, keyed not only to the objective function but to other elements such as values of variables, direction of search, and levels of feasibility and infeasibility. This creates a more flexible search behavior and joins naturally with the use of memory-based strategies that are the hallmark of tabu search approaches. Embodied particularly in the strategic oscillation component of tabu search, this nonmonotonic control has been shown in a variety of studies to yield outcomes superior to those of simulated annealing and threshold acceptance. The question arises whether such an approach offers a sufficiently rich source of search trajectories to be relied upon as a primary guidance mechanism, with greatly reduced reliance on forms of memory customarily used in tabu search. To provide an easily implemented method of this type we propose a tabu thresholding approach, which joins prescriptions of strategic oscillation with a candidate list procedure derived from network optimization studies. The candidate list and tabu search philosophies are mutually reinforcing, and the computational advantages contributed by these elements, documented by studies cited in this paper, motivate a closer look at combining them. The result yields a method with a significant potential for variation and an ability to take advantage of special structure.