Simulated annealing and tabu search: Lessons from a line search

Two prominent techniques for finding near optimal solutions to hard combinatorial optimization problems are simulated annealing and tabu search. This paper describes some methods of determining the expected time to encounter an optimal solution. The methods are used in the analysis of the performance of these two algorithms when applied to a line search. The results provide rationalization of decisions made by many algorithm designers and some insights useful for future designs.