.png){kind=icon}
.png){kind=icon}
Return
Modeling and solving the angular constrained minimum spanning tree problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2019.104775.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Combinatorial optimization
Angular constrained spanning trees
Branch-and-cut algorithms
Polyhedral combinatorics
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W