Network flow models for designing diameter‐constrained minimum‐spanning and Steiner trees
Network flow models for designing diameter‐constrained minimum‐spanning and Steiner trees
复制标题
用于设计直径约束最小跨度树和斯坦纳树的网络流模型
作者：
Luís Gouveia;T. Magnanti
我们制定并计算测试了直径约束最小生成树和斯坦纳树问题的几个模型，这些模型寻求最小成本生成树或斯坦纳树，该树受到任何节点对之间树中边数的（直径）限制。每对节点对应一种商品的传统多商品流模型在计算 1 周后无法解决 20 节点和 100 边的生成树问题。相比之下，新模型能够在不到 1 秒的时间内最优地解决这个问题，甚至可以解决多达 100 个节点和 1000 个边的更大问题实例。最大的模型包含超过 250,000 个整数变量和超过 125,000 个约束。新模型同时找到具有中心节点或中心边缘的有向树，作为具有跳跃约束的多商品流模型中的商品源。我们的结果证明了使用单一来源与其他重新配制技术相结合的力量：指导模型和使用啤酒花指数配方。当直径界限为奇数时，增强功能可以改进模型（这些情况更难解决）。本文讨论的最佳公式的线性规划松弛总是为问题的两个特殊的、多项式可解的情况给出最优整数解。 © 2003 Wiley 期刊公司。
We formulate and computationally test several models for the Diameter‐Constrained Minimum Spanning and Steiner Tree Problems, which seek a least‐cost spanning or Steiner tree subject to a (diameter) bound imposed on the number of edges in the tree between any node pair. A traditional multicommodity flow model with a commodity for every pair of nodes was unable to solve a 20‐node and 100‐edge spanning tree problem after 1 week of computation. In contrast, the new models were able to optimality solve this problem in less than 1 second and larger problem instances with up to 100 nodes and 1000 edges. The largest model contains more than 250,000 integer variables and more than 125,000 constraints. The new models simultaneously find a directed tree with a central node or a central edge that serve as a source for the commodities in a multicommodity flow model with hop constraints. Our results demonstrate the power of using single‐sourcing combined with other reformulation techniques: directing the model and using hop‐indexed formulations. Enhancements improve the models when the diameter bound is odd (these situations are more difficult to solve). The linear programming relaxation of the best formulations discussed in this paper always give an optimal integer solution for two special, polynomially solvable cases of the problem. © 2003 Wiley Periodicals, Inc.