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

小行星9301751 本研究的目的是开发，实施和测试实用的算法，在电信的各个领域的优化问题。 要研究的问题出现在具体的设置，并具有从计算的角度来看是非常棘手的共同特点，重点将是建立实验上的实际和理论上健全的算法。 第一个感兴趣的领域涉及本地接入网络中的容量扩展问题。 从整数规划的角度来看，由此产生的优化问题是相当棘手的。 然而，我们最近开发了一个快速和准确的启发式的变体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. ***