Next-generation algorithms for network layout

下一代网络布局算法

• 批准号: 9706029
• 负责人: Daniel Bienstock
• 金额: $ 25.98万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1997
• 资助国家: 美国
• 起止时间: 1997-09-15 至 2001-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9706029&HistoricalAwards=false
• 关键词: Next; generation; algorithms; network; layout

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.

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