Next-generation algorithms for network layout

几乎每一个主要的电信公司在美国，以及许多国外，有一个小组负责网络布局算法。由于升级和扩展网络需要大量投资，特别是在ATM技术的情况下，这是一个日益增长的趋势——单个大型交换机可能要花费数百万美元。通常，工作集中在出现的单个问题上，结果算法（无论是完全启发式的还是基于彻底基础的技术）严重依赖于手头问题的许多特定细节。大学里的研究人员也采用了类似的方法。除了完全通用的优化技术（如通用整数编程代码或模拟退火等启发式方法）通常不能令人满意之外，不存在成功的通用方法。然而，各种类型的网络布局问题都有许多共同的组成部分。我们对这个问题的看法是由我们在实际的ATM机布局问题上的经验所激发的。在ATM网络布局中，出现了几个相互关联的子问题。这里有一个传输系统子问题：在每条链路上必须安装足够的容量来承载在其上路由的流量。还有一个类似的交换机大小子问题（只不过容量是安装在节点上，而不是安装在链路上）。可能还有一个关于交换机终端分配的子问题，也是类似的性质。最后，可能允许不同类型的路由，例如，要求生存性。因此，处理此类复杂问题的算法可能需要很好地处理每个子问题（如果子问题在特定应用程序中成本占主导地位），但也需要将不同的组件集成到一个连贯的单个单元中（例如，边缘传输系统子问题将与交换机大小子问题相互作用）。网络设计问题可以被分类为混合整数方案：y涉及必须取整数值的变量（例如在特定链路上安装的传输系统的数量）和连续变量（主要是流量路由决策，它可以有效地建模而不需要完整性）。从计算的角度来看，这些问题通常是非常困难的。就其提供的解决方案的质量而言，纯粹的启发式算法是出了名的不可靠。另一方面，复杂的网络设计问题通常会击败高性能的通用整数规划算法。参见MIPLIB家族的“dano3mip”和“danoint”问题（http://www.caam.rice.edu/~bixby/miplib/miplib.html）以及PI以前工作中的其他问题。支持通用网络设计算法的最后一个论点涉及网络设计在实践中使用的一种方式。没有一个网络规划者会因为一个优化算法的一次运行而花费数百万美元，不管这个算法有多好的记录。通常，算法将用于反复运行设计工具的研究环境中。在这里，获得快速、高质量的评估是至关重要的。该奖项支持的研究重点是开发通用网络设计工具。我们计划开发这样一个工具的几个相当独立的组件，主要是：*在网络布局问题中出现的连续线性程序的快速，近似算法，特别是用于共享内存环境的并行化版本。*我们感兴趣的混合整数程序的一般“切割平面”技术，以及*快速舍入启发式，以快速获得良好的可行解。

Nearly every single major telecommunications concern in the United States, as well as many abroad, has a group responsible for network layout algorithms. This is a growing trend, spurred by the large investments needed to upgrade and expand networks, especially in the case of ATM technology --a single large switch can cost millions of dollars. Typically, work focuses on individual problems as they arise, and the resulting algorithms (whether completely heuristic or based on thoroughly grounded techniques) heavily depend on many particular details of the problem at hand. A similar approach is used by researchers at universities. Other than completely general optimization techniques --such as general purpose integer programming codes or heuristics such as simulated annealing-- which usually do not prove satisfactory, no successful common approach exists. However, network layout problems of all flavors do share many common components. Our views on this matter were spurred by our experience with practical ATM layout problems. In ATM network layout several interrelated subproblems arise. There is a transmission system subproblem: on every link enough capacity must be installed to carry the traffic routed on it. There is a similar switch sizing subproblem (except that capacity is installed at nodes, not links). There may be a further subproblem concerning allocation of terminations at switches, again of a similar nature. Finally, different types of routings may be allowed, for example, requiring survivability. An algorithm for a complex problem of this type may therefore need to handle each subproblem well (in case that subproblem is cost-dominant in a particular application) but would also need to integrate the different components into a coherent single unit (for example, the edge transmission system subproblem will interact with the switch sizing subproblem). Network design problems can be classifed as mixed-integer programs: the y involve variables that must take integral values (e.g. the number of transmission systems to install in a particular link) and also continuous variables (mainly traffic routing decisions, which are effectively modeled without requiring integrality). From a computational viewpoint these problems are typically very difficult. Purely heuristic algorithms are notoriously unreliable in terms of the quality of the solutions they provide. At the other end difficult network design problems routinely trounce high-performance general-purpose integer programming algorithms. See problems "dano3mip" and "danoint" of the MIPLIB family (http://www.caam.rice.edu/~bixby/miplib/miplib.html) and other problems in the PI's previous work. A final argument in favor of a general-purpose network design algorithm, concerns one way in which network design is used in practice. No network planner will commit to an expenditure of several million dollars on the basis of a single run of an optimization algorithm, no matter how good a track record this algorithm has. Typically, an algorithm would be used in the context of a study where a design tool is run repeatedly. Here it is crucial to get fast, good-quality estimates. The research supported by this award focuses in developing a generic network design tool. We plan to develop several fairly independent components of such a tool, principally: * Fast, approximate algorithms for continuous linear programs arising in network layout problems, in particular, parallelizable versions thereof for a shared-memory environment. * General "cutting-plane" techniques for the mixed-integer programs we are interested in, and * Fast rounding heuristics to quickly obtain good feasible solutions.