A cutoff time strategy based on the coupon collector's problem

Throughout the course of an optimization run, the probability of yielding further improvement becomes smaller as the search proceeds, and eventually the search stagnates. Under such a state, letting the algorithm continue to run is a waste of time as there is little hope that subsequent improvement can be made. The ability to detect the stagnation point is therefore of prime importance. If such a point can be detected reliably, then it is possible to make better use of the computing resources, perhaps restarting the algorithm at the stagnation point, either with the same or with a different parameter configuration. This paper proposes a cutoff time strategy. It presents a method that is able to reliably detect the stagnation point for one-point stochastic local search algorithms applied to combinatorial optimization problems. The strategy is derived from the coupon collector's problem, and is scalable based on the employed perturbation operator and its induced neighbourhood size, as well as from feedback from the search. The suitability and scalability of the method is illustrated with the Late Acceptance Hill-Climbing algorithm on a comprehensive set of benchmark instances of three well-known combinatorial optimization problems: the Travelling Salesman Problem, the Quadratic Assignment Problem, and the Permutation Flowshop Scheduling Problem.