Modeling and solving the angular constrained minimum spanning tree problem

Assume one is given an angle alpha is an element of(0, 2 pi] and a complete undirected graph G = (V, E). The vertices in V represent points in the Euclidean plane. The edges in E represent the line segments between these points, with edge weights equal to segment lengths. Spanning trees of G are called alpha-spanning trees (alpha-STs) if, for any i is an element of V, the smallest angle that encloses all line segments corresponding to its i-incident edges does not exceed alpha. The Angular Constrained Minimum Spanning Tree Problem (alpha-MSTP) seeks an alpha-ST with the least weight. The problem arises in the design of wireless communication networks operating under directional antennas. We propose two alpha-MSTP formulations. One, F-x requiring, in principle, O(2(vertical bar V vertical bar)) inequalities to model the angular constraints (alpha-AC). For alpha is an element of(0, pi), however, we show that just O(vertical bar V vertical bar(3)) of them suffice to attain not only a formulation but also the same Linear Programming relaxation (LPR) bound as the full blown model. The other formulation, F-xy, enlarges the set of F-x variables but manages to model alpha-AC, compactly. Furthermore, F-xy LPR bounds are proven to dominate their F-x counterparts. That dominance, however, is empirically shown to reduce as alpha increases. Finally, exact Branch-and-Cut algorithms implemented for the two formulations are shown, empirically, to exchange roles as top performer, throughout the [0, 2 pi) range of alpha values. (C) 2019 Elsevier Ltd. All rights reserved.