论文标题
改进了角度约束最小跨越树问题的配方和分支切割算法
Improved Formulations and Branch-and-cut Algorithms for the Angular Constrained Minimum Spanning Tree Problem
论文作者
论文摘要
角度约束的最小跨越树问题（$α$ -MSTP）是根据完整的无向图$ g =（v，e）$和$ g $的角度$α\的角度定义的。 $α$式树（$α$ -ST）的$ g $，如果$ i \ in V $，将所有线段的最小角度与其$ i $ incients Edges相对应f} _ {xy}^*$和$ \ MATHCAL {f} _X^{++} $及其随附的分支和切口（BC）算法，BCFXY $^*$^*$和BCFX $^{++^{++} $。 $ \ MATHCAL {F} _X^{++} $，通过：（i）举起一组现有的不平等现象，负责执行$α$角约束，并且（ii）表征$α$ -MSTP有效的不平等现象，请从稳定的polytope，$α-$ STS的结构中披露，在此处披露了这些结构。从数值的角度来看，多面的角度，我们观察到BCFXY $^*$和BCFX $^{++} $实际上与他们的竞争对手相比$α-$ MSTP算法能够求解更多实例，以证明最佳性并提供更清晰的下限，而在强加的时间限制中没有证明最佳性。
The Angular Constrained Minimum Spanning Tree Problem ($α$-MSTP) is defined in terms of a complete undirected graph $G=(V,E)$ and an angle $α\in (0,2π]$. Vertices of $G$ define points in the Euclidean plane while edges, the line segments connecting them, are weighted by the Euclidean distance between their endpoints. A spanning tree is an $α$-spanning tree ($α$-ST) of $G$ if, for any $i \in V$, the smallest angle that encloses all line segments corresponding to its $i$-incident edges does not exceed $α$. $α$-MSTP consists in finding an $α$-ST with the least weight. We introduce two $α-$MSTP integer programming formulations, ${\mathcal F}_{xy}^*$ and $\mathcal{F}_x^{++}$ and their accompanying Branch-and-cut (BC) algorithms, BCFXY$^*$ and BCFX$^{++}$. Both formulations can be seen as improvements over formulations coming from the literature. The strongest of them, $\mathcal{F}_x^{++}$, was obtained by: (i) lifting an existing set of inequalities in charge of enforcing $α$ angular constraints and (ii) characterizing $α$-MSTP valid inequalities from the Stable Set polytope, a structure behind $α-$STs, that we disclosed here. These formulations and their predecessors in the literature were compared from a polyhedral perspective. From a numerical standpoint, we observed that BCFXY$^*$ and BCFX$^{++}$ compare favorably to their competitors in the literature. In fact, thanks to the quality of the bounds provided by $\mathcal{F}_x^{++}$, BCFX$^{++}$ seems to outperform the other existing $α-$MSTP algorithms. It is able to solve more instances to proven optimality and to provide sharper lower bounds, when optimality is not attested within an imposed time limit. As a by-product, BCFX$^{++}$ provided 8 new optimality certificates for instances coming from the literature.
