Overview
Constrained Optimization problems are ubiquitous, whether one is interested in the design of an integrated circuit or a car, the production of a factory schedule, or the routing of school buses. One promising approach to solving these problems involves using Simulated Annealing (SA) search. This is a stochastic neighborhood search procedure that moves from one solution to another, while recording the best solution found so far. Typically, the procedure attempts to move to solutions that improve over the current one, though occasionally transitions to lower quality solutions are accepted in an attempt to avoid local optima. SA has been shown to yield near-optimal solutions to many difficult combinatorial optimization problems, if run a sufficiently large number of times. Our research in this area has aimed at developing adaptive mechanisms to speedup SA search. Specifically, we have developed and experimented with the following two techniques:

• Speedup Learning Techniques for SA Search - The idea here is to learn, over multiple SA runs on a given problem, to recognize (un)promising runs and use this knowledge to decide when to abandon a run and where to restart new ones [Sadeh et al., 97]. These techniques have been shown to yield important speedups and/or yield solution improvements on two classes of problems: just-in-time job shop scheduling problems and vehicle routing problems with time windows
• Focused Simulated Annealing Search - Focused Simulated Annealing (FSA) aims at reducing the risks of getting trapped in local optima by dynamically inflating the costs associated with major inefficiencies in the current solution [Sadeh and Nakakuki, 96]. This approach has been validated on just-in-time job shop scheduling problems where it was shown to yield important speedups, especially on problems where the original SA procedure was most likely to get trapped in local optima.

Personnel

• Norman Sadeh

Collaborators

• Ramesh Bollapragada
• Sam R. Thangiah
• Yoichiro Nakakuki

Publications

		1997
[Sadeh et al., 97]		Norman M. Sadeh, Yoichiro Nakakuki, and Sam R. Thangiah. Learning to Recognize (Un)Promising Simulated Annealing Runs: Efficient Search Procedures for Job Shop Scheduling and Vehicle Routing. Annals of Operations Research, 75, 1997, pp. 189-208.
		1996
[Sadeh and Nakakuki, 96]		Norman M. Sadeh and Yoichiro Nakakuki. Focused Simulated Annealing Search: An Application to Job Shop Scheduling. Annals of Operations Research, 60, 1996, pp. 77-103. Special issue on Metaheuristics in Combinatorial Optimization. Also available as CMU Robotics Institute Technical Report CMU-RI-TR-94-29.

back to top