Many discrete optimization problems amount to select a feasible subgraph of least weight. We consider in this paper the context of spatial graphs where the positions of the vertices are uncertain and belong to known uncertainty sets. The objective is to minimize the sum of the distances in the chosen subgraph for the worst positions of the vertices in their uncertainty sets. We first prove that these problems are NP-hard even when the feasible subgraphs consist either of all spanning trees or of all s-t paths. In view of this, we propose en exact solution algorithm combining integer programming formulations with a cutting plane algorithm, identifying the cases where the separation problem can be solved efficiently. We also propose two types of polynomial-time approximation algorithms. The first one relies on solving a nominal counterpart of the problem considering pairwise worst-case distances. We study in details the resulting approximation ratio, which depends on the structure of the metric space and of the feasible subgraphs. The second algorithm considers the special case of s-t paths and leads to a fully-polynomial time approximation scheme. Our algorithms are numerically illustrated on a subway network design problem and a facility location problem.
翻译:许多离散优化问题相当于选择一个最小重量的可行子图。 我们在本文件中考虑空间图的背景, 其中脊椎的位置不确定, 属于已知的不确定组。 目标是将所选脊椎最差位置在不确定组中所选子图的距离总和最小化。 我们首先证明, 这些问题是NP- 硬化的, 即使可行的子图由横跨所有树或所有小路径组成。 有鉴于此, 我们提出精确的解算法, 将整形编程配方与切除平面算法相结合, 确定分离问题可以有效解决的个案。 我们还提出了两种多米时近似算法。 第一项取决于对称最差距离问题的名义对应法。 我们研究由此产生的近似率, 这取决于测量空间的结构以及可行的子图。 第二种算法考虑了 s- t 路径的特殊案例, 并导致一个完全极化的时间近似方案。 我们的算法是在地铁网络设计问题和设施位置问题上用数字说明的。