Computational Optimization Problems in Local Access Networks, SONET Rings and Lightwave

9301751 Bienstock这项研究的目的是开发、实施和测试用于电信各个领域的优化问题的实用算法。要研究的问题出现在具体的环境中，从计算的角度来看，它们具有极其棘手的共同特征；重点将放在建立实验上实用和理论上合理的算法上。第一个感兴趣的领域涉及本地接入网络中的容量扩展问题。从整数规划的角度来看，由此产生的优化问题是相当棘手的。然而，我们最近为Bellcore在计划中使用的这个问题的一个变体开发了一个快速而准确的启发式；我们计划扩展分析和启发式，以处理更复杂和详细的模型。第二个问题是SONET环的问题。这是一个在不久的将来将变得越来越重要的新兴领域，并且在该上下文中出现了许多重要的优化问题(例如，将容量分配给给定环SA以处理环中节点之间的业务请求)。最后一个问题涉及光波网络。已经受到一些关注的问题是将频率分配给网络中的发送器和接收器，然后在所得到的逻辑网络中路由业务请求，从而在所有可能的频率分配和路由上实现最小拥塞。这是一个极其棘手的优化问题；然而，专用算法的初步经验令人鼓舞。研究这些问题的方法将包括开发新工具所需的理论分析，以及在最近成功工作的基础上实施结果算法，并进一步强调结果代码的速度和实用性。***

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. ***