9301751 Bienstock The purpose of this research is to develop, implement, and test practical algorithms for optimization problems in various areas of telecommunications. The problems to be studied arise in concrete settings and have the common feature of being extremely intractable from a computational viewpoint; the focus will be on building experimentally practical and theoretically sound algorithms. The first area of interest concerns capacity expansion problems in local access networks. The resulting optimization problems turn out to be rather intractable from the point of view of integer programming. However, we have recently developed a fast and accurate heuristic for a variant of this problem used by Bellcore in its planning; we plan to extend the analysis and the heuristic to handle more complex and detailed models. The second problem area is that of SONET rings. This is an emerging field which will be for increasing importance in the near future, and there are many important optimization problems that arise in this context (for example, the assignment of capacity to a given ring sa as to handle traffic requests between the nodes in the ring). The last problem area concerns lightwave networks. A problem that has received some attention is that of assigning frequencies to the transmitters and receivers in a network, and then to route traffic requests in the resulting logical network, sa as to achieve minimum congestion over all possible frequency assignments and routings. This is an extremely intractable optimization problem; nevertheless, preliminary experience with a special-purpose algorithm has been encouraging. The approach for studying these problems will encompass both the theoretical analysis needed to develop new tools, and , building upon successful recent work, the implementation of resulting algorithms, with added emphasis on speed and practicality of the resulting code. ***
