Multicommodity network design with discrete node costs
Multicommodity network design with discrete node costs
复制标题
具有离散节点成本的多商品网络设计
DOI：
10.1002/net.20144
复制
发表时间：
2007
期刊：
影响因子：
2.1
通讯作者：
L. Brunetta
中科院分区：
文献类型：
--
作者：
P. Belotti;F. Malucelli;L. Brunetta
虽然有大量的文献涉及网络设计，很少有人关注的网络与复杂的节点成本。虽然节点成本线性地依赖于总的通过流量，可以很容易地嵌入到更常见的具有链路成本的网络框架中，但是当节点成本是例如安装在节点中的设施的逐步函数时，这不再是可能的。这一特点在现代电信网络中似乎是至关重要的，但在其他领域也有应用，在这些领域，可用的技术有限，容量和成本值不连续。在我们的具体应用中，我们提出了一个数学规划模型，明确占节点成本是逐步与非线性增量。两个家庭的有效的不等式，然后介绍，其中之一是在以前的工作中提出的Stoer和Dahl的多设施网络模型的扩展。由于这些不等式的分离问题是困难的，我们开发了一个启发式分离过程。我们设计了一个分支和切割方法，并在网络设计文献中找到的一组真实的实例上对其进行测试。这种新的方法被证明是有效的商业通用MIP算法相比。© 2006 Wiley Periodicals，Inc. NETWORKS，Vol. 49（1），90-99 2007
Although there is an extensive literature dealing with network design, little attention has been devoted to networks with complicated node costs. Although node costs, depending linearly on the total passing flow, can be easily embedded into the more usual framework of networks with link costs, when the node costs are, for instance, a stepwise function of the facilities installed into the nodes, this is no longer possible. This feature seems to be crucial in modern telecommunications networks, but has also applications in other fields, where a limited set of technologies is available with discrete values of capacities and costs. In our specific application, we propose a mathematical programming model that explicitly accounts for node costs that are stepwise with nonlinear increments. Two families of valid inequalities are then introduced, one of which is an extension of those presented in a previous work by Stoer and Dahl for multifacility network models. As the separation problem for these inequalities is difficult, we develop a heuristic separation procedure. We devise a branch‐and‐cut method and test it on a set of real‐world instances found in the network design literature. This new method proves to be efficient when compared to a commercial general purpose MIP algorithm. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 49(1), 90–99 2007