Gollowitzer Stefan, Ljubić Ivana
Department of Statistics and Decision Support Systems, Faculty of Business, Economics, and Statistics, University of Vienna, Austria.
Comput Oper Res. 2011 Feb;38(2):435-449. doi: 10.1016/j.cor.2010.07.002.
This article comprises the first theoretical and computational study on mixed integer programming (MIP) models for the connected facility location problem (ConFL). ConFL combines facility location and Steiner trees: given a set of customers, a set of potential facility locations and some inter-connection nodes, ConFL searches for the minimum-cost way of assigning each customer to exactly one open facility, and connecting the open facilities via a Steiner tree. The costs needed for building the Steiner tree, facility opening costs and the assignment costs need to be minimized. We model ConFL using seven compact and three mixed integer programming formulations of exponential size. We also show how to transform ConFL into the Steiner arborescence problem. A full hierarchy between the models is provided. For two exponential size models we develop a branch-and-cut algorithm. An extensive computational study is based on two benchmark sets of randomly generated instances with up to 1300 nodes and 115,000 edges. We empirically compare the presented models with respect to the quality of obtained bounds and the corresponding running time. We report optimal values for all but 16 instances for which the obtained gaps are below 0.6%.
本文包含了对连通设施选址问题（ConFL）的混合整数规划（MIP）模型的首次理论和计算研究。ConFL结合了设施选址和斯坦纳树：给定一组客户、一组潜在设施位置和一些互连节点，ConFL搜索将每个客户精确分配到一个开放设施，并通过斯坦纳树连接这些开放设施的最低成本方式。构建斯坦纳树所需的成本、设施开放成本和分配成本需要最小化。我们使用七个紧凑的和三个指数规模的混合整数规划公式对ConFL进行建模。我们还展示了如何将ConFL转化为斯坦纳树形图问题。提供了模型之间的完整层次结构。对于两个指数规模的模型，我们开发了一种分支切割算法。一项广泛的计算研究基于两组随机生成的基准实例集，这些实例最多有1300个节点和115,000条边。我们根据获得的界的质量和相应的运行时间对所提出的模型进行实证比较。对于除16个实例之外的所有实例，我们报告了最优值，这些实例获得的差距低于0.6%。
