Next-generation algorithms for network layout

美国几乎每一家主要的电信公司，以及国外的许多公司，都有一个负责网络布局算法的小组。这是一种日益增长的趋势，原因是升级和扩大网络所需的大量投资，特别是在ATM技术的情况下--一台大型交换机的成本可能高达数百万美元。通常，工作的重点是单个问题出现时，结果算法(无论是完全启发式的还是基于完全扎根的技术)在很大程度上依赖于手头问题的许多特定细节。大学的研究人员也使用了类似的方法。除了完全通用的优化技术--例如通用整数编程代码或模拟退火法之类的启发式方法--通常不能令人满意之外，没有成功的通用方法。然而，所有类型的网络布局问题都有许多共同的组成部分。我们对这一问题的看法是受到我们在ATM实际布局问题上的经验的启发。在ATM网络布局中，出现了几个相互关联的子问题。有一个传输系统的子问题：在每条链路上必须安装足够的容量来承载在其上路由的流量。还有一个类似的交换机规模确定子问题(只是容量安装在节点上，而不是链路上)。可能还有另一个关于交换机端接分配的子问题，同样具有类似的性质。最后，可以允许不同类型的路由，例如，需要生存性。因此，这种类型的复杂问题的算法可能需要很好地处理每个子问题(如果该子问题在特定应用中是成本主导的)，但还需要将不同的组件集成到一致的单个单元中(例如，边缘传输系统子问题将与交换机尺寸子问题交互作用)。网络设计问题可以归类为混合整数规划：y涉及必须取整数值的变量(例如，在特定链路中安装的传输系统的数量)以及连续变量(主要是业务路由决策，其被有效地建模而不要求完整性)。从计算的角度来看，这些问题通常是非常困难的。就它们提供的解决方案的质量而言，纯粹的启发式算法是出了名的不可靠。另一方面，困难的网络设计问题通常会击败高性能的通用整数规划算法。见问题“dano3mip”和“danoint”的MIPLIB族(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.