
























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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。