2-InterConnected Facility Location: Specifications, Complexity Results, and Exact Solutions
2-InterConnected Facility Location: Specifications, Complexity Results, and Exact Solutions
复制标题
2-互连设施位置：规格、复杂性结果和精确解决方案
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
M. Martens
中科院分区：
文献类型：
--
作者：
Markus Chimani;Maria Kandyba;M. Martens
。互联设施选址问题结合了低成本的fi低成本设施布置(包括廉价的客户到设施连接)和设施之间相互连接的要求。例如，在网络由中央核心和必须连接到它的本地客户端组成的电信应用中，出现这样的网络设计问题。在实践中，核心网络的可靠性是一个中心问题，因此我们可能要求核心网络(至少)2-互连，即在核心网络内每对核心节点之间有两条不相交的路径。建立了2-互连设施选址(2-iCFL)的问题类，对其中心变量进行了分类，并证明了它们是难以逼近的。然而，正如我们的计算结果所显示的，基于割的ILP公式，也在这里提出，允许我们有效地解决这样的问题到数百个节点的最优。在此过程中，我们为允许2-iCFL可行解的问题实例建立了简单而详尽的刻画。这些特征是建设性的，可用于算法可行性检查、预处理步骤和启发式方法。
. Connected facility location problems combine cost-efficient facility placement (including cheap client-to-facility-connection) with the requirement to connect the facilities among each other. Such network design problems arise, e.g., in telecommunication applications where networks consist of a central core and local clients that have to be connected to it. In practice, reliability of the core network is a central issue, and we may hence require the core network to be (at least) 2-interconnected, i.e., there are two disjoint paths within the core network between every pair of core nodes. We establish the problem class of 2-interConnected Facility Location (2-iCFL), categorize its central variants, and prove that they are hard to approximate. However, as our computational results show, cut-based ILP formulations, also presented herein, allow us to effectively solve such problems to optimality for hundreds of nodes. On the way, we establish simple but exhaustive characterizations for problem instances admitting feasible solutions for 2-iCFL. These characterizations are constructive and can be used for algorithmic feasibility checks, preprocessing steps, and heuristics.