On simulated annealing in EDA

Simulated annealing was first introduced in 1983 as a generic stochastic algorithmic approach to solve optimization problems. Prof. C. L. Liu and his students H. W. Leong and D. F. Wong were among the earliest EDA researchers who applied simulated annealing to EDA. They solved a wide range of EDA problems with successes and reported their results in a series of papers at premier EDA conferences such DAC and ICCAD. Liu, Leong, and Wong later summarized their works in a research monograph entitled Simulated Annealing for VLSI Design, published in 1988 by Kluwer Academic Publishers. In the Preface of their book, the authors wrote "We hope that our experiences with the techniques we employed, some of which indeed bear certain similarities for different problems, could be useful as hints and guides for other researchers in applying the method to the solutions of other problems". Indeed, there were "similarities in techniques" among Liu's works that had influenced the design of simulated annealing EDA algorithms in the past 20 some years. To better understand Liu's contributions in simulated annealing, one should note that a typical simulated annealing algorithm uses a solution space and a cost function that come directly with the problem. Although computation time may be high, the algorithm is straightforward to design, making simulated annealing an attractive option for difficult problems where clever algorithms are hard to come by. On the contrary, Liu's simulated annealing algorithms have a completely different style: They resemble clever algorithms that attempt to solve difficult problems in polynomial time, and they often have a strong algorithmic flavor with a significant effort spent on optimizing the solution space and cost function. In this talk, we will discuss Prof. Liu's pioneering contributions in simulated annealing for EDA.