×

Modeling and solving the angular constrained minimum spanning tree problem. (English) Zbl 1458.90623

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.

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

Software:

XPRESS; TSPLIB
PDFBibTeX XMLCite
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.