Mixed-integer programming approaches for the tree $$t^*$$t∗-spanner problem
Mixed-integer programming approaches for the tree $$t^*$$t∗-spanner problem
复制标题
树 $$t^*$$t*-spanner 问题的混合整数规划方法
作者：
Eduardo Álvarez;Markus Sinnl
树$$t^*$t-树问题是一个NP-难问题，它涉及在给定的无向加权图中找到一棵生成树，使得对于每对节点，生成树中的最短距离与给定图中的最短距离之比以t为界。我们的目标是找到一棵生成树，它给出了最小的t。这个问题与许多网络设计应用程序，但特别是在分布式系统的架构的上下文中。我们介绍了混合整数规划公式的树$$t^*$$$t规划问题，并提出了一个分支和切割解决方案的基础上，这些公式。分支和切割增强了初始化过程和原始启发式。一个计算的研究，以评估我们提出的算法策略的有效性。据我们所知，这是第一次提出一个确切的方法来解决这个问题。
The tree $$t^*$$t∗-spanner problem is an NP-hard problem, which is concerned with finding a spanning tree in a given undirected weighted graph, such that for each pair of nodes the ratio of the shortest distance in the spanning tree and the shortest distance in the given graph is bounded by t. The goal is to find a spanning tree, which gives the minimal t. This problem is associated with many network design applications, but in particular, in the context of architecture of distributed systems. We introduce mixed-integer programming formulations for the tree $$t^*$$t∗-spanner problem, and present a branch-and-cut solution approach based on these formulations. The branch-and-cut is enhanced with an initialization procedure and a primal heuristic. A computational study is done to assess the effectiveness of our proposed algorithmic strategies. To the best of our knowledge, this is the first time that an exact approach is proposed for this problem.