Research Initiation: Capacitated Network Design; Solution Approaches Based on Integer and Linear Programming

研究启动：能力网络设计；

• 批准号: 9210979
• 负责人: Leslie Hall
• 金额: $ 6万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1992
• 资助国家: 美国
• 起止时间: 1992-08-01 至 1995-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9210979&HistoricalAwards=false
• 关键词: Research; Initiation; Capacitated; Network; Design

Network design encompasses an array of problems as diverse as vehicle routing, facility location, and telecommunications. Problems in this area naturally fall into two types: capacitated and uncapacitated, according to whether potential edges in (or flows through) the network are capacitated. While uncapacitated network design problems are well studied and reasonably tractable, capacitated problems seem to be considerably more difficult, in part because good integer programming formulations for them are largely unknown. This research will focus on an important network design model, the problem of designing a centralized processing network. This research will focus on the development and implementation of cutting-plan algorithms, based on linear programming, for several variants of this problem.

网络设计包含一系列不同的问题，如车辆路线、设施位置和电信。根据网络中的潜在边缘（或流过的边缘）是否被容限，这一领域的问题自然分为容限和无容限两类。虽然无容量的网络设计问题得到了很好的研究，并且相当容易处理，但有容量的问题似乎要困难得多，部分原因是它们的良好整数规划公式在很大程度上是未知的。本文将重点研究一个重要的网络设计模型，即集中处理网络的设计问题。本研究将集中于基于线性规划的切割计划算法的开发和实现，用于解决该问题的几个变体。