Salles da Cunha, Alexandre; Lucena, Abilio Modeling and solving the angular constrained minimum spanning tree problem. (English) Zbl 1458.90623 Comput. Oper. Res. 112, Article ID 104775, 15 p. (2019). Summary: Assume one is given an angle \(\alpha \in (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 \in 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, \(\mathcal{F}_x\) requiring, in principle, \(O(2^{|V|})\) inequalities to model the angular constraints (\(\alpha\)-AC). For \(\alpha \in (0, \pi)\), however, we show that just \(O(|V|^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, \(\mathcal{F}_{x y}\), enlarges the set of \(\mathcal{F}_x\) variables but manages to model \(\alpha\)-AC, compactly. Furthermore, \(\mathcal{F}_{x y}\) LPR bounds are proven to dominate their \(\mathcal{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. Cited in 2 Documents MSC: 90C35 Programming involving graphs or networks 68R10 Graph theory (including graph drawing) in computer science 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut Keywords:combinatorial optimization; angular constrained spanning trees; branch-and-cut algorithms; polyhedral combinatorics Software:XPRESS; TSPLIB PDFBibTeX XMLCite \textit{A. Salles da Cunha} and \textit{A. Lucena}, Comput. Oper. Res. 112, Article ID 104775, 15 p. (2019; Zbl 1458.90623) Full Text: DOI References: [1] Ackerman, E.; Gelander, T.; Pinchasi, R., Ice-creams and wedge graphs, Comput. Geom., 46, 213-218 (2013) · Zbl 1360.68636 [2] Aschner, R.; Katz, M. J., Bounded-angle spanning tree: modeling networks with angular constraints, Algorithmica, 77, 349-373 (2017) · Zbl 1359.68229 [3] Carmin, P.; Katz, M. J.; Lotker, Z.; Rosén, A., Connectivity guarantees for wireless networks with directional antennas, Comput. Geom., 44, 477-485 (2011) · Zbl 1233.05123 [4] Cormen, T.; Leiserson, C.; Rivest, R., Introduction to Algorithms (2009), MIT Press · Zbl 1187.68679 [5] Dolan, E. D.; Moré, J. J., Benchmark optimization software with performance profiles, Math. Program., 91, 2, 201-213 (2002) · Zbl 1049.90004 [6] Edmonds, J., Matroids and the greedy algorithm, Math. Program., 1, 1, 127-136 (1971) · Zbl 0253.90027 [7] Kruskal, J., On the shortest spanning subtree of a graph and the traveling salesman problem, Proc. Am. Math. Soc., 7, 48-50 (1956) · Zbl 0070.18404 [8] Padberg, M.; Rinaldi, G., A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems, SIAM Rev., 33, 1, 60-100 (1991) · Zbl 0734.90060 [9] Padberg, M. W.; Wolsey, L. A., Trees and cuts, Ann. Discrete Math., 17, 511-517 (1983) · Zbl 0522.90095 [10] Reinelt, G., TSPLIB - a traveling salesman problem library, ORSA J. Comput., 3, 4, 376-384 (1991) · Zbl 0775.90293 [11] XPRESS mixed integer optimization package, release 8.4.2017. FICO XPRESS.; XPRESS mixed integer optimization package, release 8.4.2017. FICO XPRESS. [12] Yu, Z.; Teng, J.; Bai, X.; Xuan, D.; Jia, W., Connected coverage in wireless networks with directional antennas, ACM Trans. Sens. Netw., 10, 3, 51:1-51:28 (2014) This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.