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 路径的特殊案例, 并导致一个完全极化的时间近似方案。 我们的算法是在地铁网络设计问题和设施位置问题上用数字说明的。

0
下载
关闭预览

相关内容

【最受欢迎的概率书】《概率论:理论与实例》,490页pdf
专知会员服务
162+阅读 · 2020年11月13日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
鲁棒机器学习相关文献集
专知
8+阅读 · 2019年8月18日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年10月22日
Arxiv
30+阅读 · 2021年7月7日
Arxiv
4+阅读 · 2018年11月26日
VIP会员
相关资讯
鲁棒机器学习相关文献集
专知
8+阅读 · 2019年8月18日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员