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

网络设计涉及车辆路线、设施位置和电信等一系列问题。根据网络中(或流经)的潜在边是否是容量的，这一领域的问题自然分为两种类型：容量和非容量。虽然无能力网络设计问题得到了很好的研究，并且相当容易处理，但有能力的问题似乎要困难得多，部分原因是它们的良好整数规划公式在很大程度上是未知的。本研究将重点研究一个重要的网络设计模型--集中处理网络的设计问题。这项研究将集中于基于线性规划的切割计划算法的开发和实现，以解决该问题的几个变种。

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.