English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

The Angular Constrained Minimum Spanning Tree Problem ($\alpha$-MSTP) isdefined in terms of a complete undirected graph $G=(V,E)$ and an angle $\alpha\in (0,2\pi]$. Vertices of $G$ define points in the Euclidean plane whileedges, the line segments connecting them, are weighted by the Euclideandistance between their endpoints. A spanning tree is an $\alpha$-spanning tree($\alpha$-ST) of $G$ if, for any $i \in V$, the smallest angle that enclosesall line segments corresponding to its $i$-incident edges does not exceed$\alpha$. $\alpha$-MSTP consists in finding an $\alpha$-ST with the leastweight. We introduce two $\alpha-$MSTP integer programming formulations,${\mathcal F}_{xy}^*$ and $\mathcal{F}_x^{++}$ and their accompanyingBranch-and-cut (BC) algorithms, BCFXY$^*$ and BCFX$^{++}$. Both formulationscan be seen as improvements over formulations coming from the literature. Thestrongest of them, $\mathcal{F}_x^{++}$, was obtained by: (i) lifting anexisting set of inequalities in charge of enforcing $\alpha$ angularconstraints and (ii) characterizing $\alpha$-MSTP valid inequalities from theStable Set polytope, a structure behind $\alpha-$STs, that we disclosed here.These formulations and their predecessors in the literature were compared froma polyhedral perspective. From a numerical standpoint, we observed thatBCFXY$^*$ and BCFX$^{++}$ compare favorably to their competitors in theliterature. In fact, thanks to the quality of the bounds provided by$\mathcal{F}_x^{++}$, BCFX$^{++}$ seems to outperform the other existing$\alpha-$MSTP algorithms. It is able to solve more instances to provenoptimality and to provide sharper lower bounds, when optimality is not attestedwithin an imposed time limit. As a by-product, BCFX$^{++}$ provided 8 newoptimality certificates for instances coming from the literature.

Improved Formulations and Branch-and-cut Algorithms for the Angular Constrained Minimum Spanning Tree Problem