Publication Date:
2019
Description:
〈p〉Publication date: December 2019〈/p〉
〈p〉〈b〉Source:〈/b〉 Computers & Operations Research, Volume 112〈/p〉
〈p〉Author(s): Alexandre Salles da Cunha, Abilio Lucena〈/p〉
〈h5〉Abstract〈/h5〉
〈div〉〈p〉Assume one is given an angle 〈em〉α〈/em〉 ∈ (0, 2〈em〉π〈/em〉] and a complete undirected graph 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si38.svg"〉〈mrow〉〈mi〉G〈/mi〉〈mo linebreak="goodbreak"〉=〈/mo〉〈mo〉(〈/mo〉〈mi〉V〈/mi〉〈mo〉,〈/mo〉〈mi〉E〈/mi〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉. The vertices in 〈em〉V〈/em〉 represent points in the Euclidean plane. The edges in 〈em〉E〈/em〉 represent the line segments between these points, with edge weights equal to segment lengths. Spanning trees of 〈em〉G〈/em〉 are called 〈em〉α〈/em〉-spanning trees (〈em〉α〈/em〉-STs) if, for any 〈em〉i〈/em〉 ∈ 〈em〉V〈/em〉, the smallest angle that encloses all line segments corresponding to its 〈em〉i〈/em〉-incident edges does not exceed 〈em〉α〈/em〉. The Angular Constrained Minimum Spanning Tree Problem (〈em〉α〈/em〉-MSTP) seeks an 〈em〉α〈/em〉-ST with the least weight. The problem arises in the design of wireless communication networks operating under directional antennas. We propose two 〈em〉α〈/em〉-MSTP formulations. One, 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si39.svg"〉〈msub〉〈mi mathvariant="bold-script"〉F〈/mi〉〈mi〉x〈/mi〉〈/msub〉〈/math〉 requiring, in principle, 〈em〉O〈/em〉(2〈sup〉|〈em〉V〈/em〉|〈/sup〉) inequalities to model the angular constraints (〈em〉α〈/em〉-AC). For 〈em〉α〈/em〉 ∈ (0, 〈em〉π〈/em〉), however, we show that just 〈em〉O〈/em〉(|〈em〉V〈/em〉|〈sup〉3〈/sup〉) 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, 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si40.svg"〉〈mrow〉〈msub〉〈mi mathvariant="bold-script"〉F〈/mi〉〈mrow〉〈mi〉x〈/mi〉〈mi〉y〈/mi〉〈/mrow〉〈/msub〉〈mo〉,〈/mo〉〈/mrow〉〈/math〉 enlarges the set of 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si39.svg"〉〈msub〉〈mi mathvariant="bold-script"〉F〈/mi〉〈mi〉x〈/mi〉〈/msub〉〈/math〉 variables but manages to model 〈em〉α〈/em〉-AC, compactly. Furthermore, 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si41.svg"〉〈msub〉〈mi mathvariant="bold-script"〉F〈/mi〉〈mrow〉〈mi〉x〈/mi〉〈mi〉y〈/mi〉〈/mrow〉〈/msub〉〈/math〉 LPR bounds are proven to dominate their 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si39.svg"〉〈msub〉〈mi mathvariant="bold-script"〉F〈/mi〉〈mi〉x〈/mi〉〈/msub〉〈/math〉 counterparts. That dominance, however, is empirically shown to reduce as 〈em〉α〈/em〉 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〈em〉π〈/em〉) range of 〈em〉α〈/em〉 values.〈/p〉〈/div〉
Print ISSN:
0305-0548
Electronic ISSN:
1873-765X
Topics:
Mathematics
,
Economics
Permalink