Heuristic and exact techniques for solving a temperature estimation model

This dissertation provides several techniques for solving a class of nonconvex optimization problems that arise in the thermal analysis of electronic chip packages. The topic is of interest because in systems containing delicate electronic components both performance and reliability are impacted by thermal behavior. A modeling paradigm, called Compact Thermal Modeling (CTM), has been demonstrated to show promise for accurately estimating steady state thermal behavior without resorting to computationally intensive finite element models or expensive direct experimentation. The CTM is a network model that gives rise to a nonconvex optimization problem. A solution to this nonconvex optimization problem provides a reasonably accurate characterization of the steady state temperature profile the chip will attain under arbitrary boundary conditions, which allows the system designer to model the application of a wide range of thermal design strategies with useful accuracy at reasonable computational cost. This thesis explores several approaches to solving the optimization problem. We present a heuristic technique that is an adaptation of the classical coordinate search method that has been adapted to run efficiently by exploiting the algebraic structure of the problem. Further, the heuristic is able to avoid stalling in poor local optima by using a partitioning scheme that follows from an examination of special structure in the problem's feasible region. We next present several exact approaches using a globally optimal method based on the Reformulation Linearization Technique (RLT). This approach generates and then solves convex relaxations of the original problem, tightening the approximations within a branch and bound framework. We then explore several approaches to improving the performance of the RLT technique by introducing variable substitutions and valid inequalities, which tighten the convex relaxations. Computational results, conclusions; and recommendations for further research are also provided.