9875945, Lillis, John This project studies techniques for solving combinatorial optimization problems with an emphasis on problems from CAD/VLSI. The approach is through developing a local search paradigm. In a local search algorithm a solution (for instance a standard cell placement) is iteratively improved by a sequence of moves or perturbations; the set of allowable moves defines the neighborhood structure of the algorithm (for example, pair-wise swapping in cell placement). This research studies classes of neighborhood operators with more expansive solution space coverage than traditional techniques. One such class is based on constraint relaxation. Operators with exponentially large neighborhoods are of particular interest. An orthogonal topic is the use of "meta-heuristics" in which a local-search engine can be viewed as a subroutine. Here we explore and evaluate experimentally more sophisticated techniques which attempt to focus on promising portions of the solution space. The research includes the archiving and analysis of known solutions to various optimization problems. Such known solutions are being studied via statistical and visualization techniques toward the end of finding superior optimization algorithms by better understanding of the nature of local optima of a particular problem. An in-depth study of the cell placement problem is being used as a testbed for these techniques.
