Improved formulations and branch-and-cut algorithms for the angular constrained minimum spanning tree problem

Alexandre Salles Cunha ()
Additional contact information
Alexandre Salles Cunha: Universidade Federal de Minas Gerais

Journal of Combinatorial Optimization, 2022, vol. 44, issue 1, No 19, 379-413

Abstract: Abstract The Angular Constrained Minimum Spanning Tree Problem ( $$\alpha $$ α -MSTP) is defined in terms of a complete undirected graph $$G=(V,E)$$ G = ( V , E ) and an angle $$\alpha \in (0,2\pi ]$$ α ∈ ( 0 , 2 π ] . Vertices of G define points in the Euclidean plane while edges, the line segments connecting them, are weighted by the Euclidean distance between their endpoints. A spanning tree is an $$\alpha $$ α -spanning tree ( $$\alpha $$ α -ST) of G if, for any $$i \in V$$ i ∈ V , the smallest angle that encloses all line segments corresponding to its i-incident edges does not exceed $$\alpha $$ α . $$\alpha $$ α -MSTP consists in finding an $$\alpha $$ α -ST with the least weight. In this work, we discuss families of $$\alpha $$ α -MSTP valid inequalities. One of them is a lifting of existing angular constraints found in the literature and the others come from the Stable Set polytope, a structure behind $$\alpha $$ α -STs disclosed here. We show that despite being already satisfied by the previously strongest known formulation, $${\mathcal {F}}_{xy}$$ F xy , these lifted angular constraints are capable of strengthening another existing $$\alpha $$ α -MSTP model so that both become equally strong, at least for the instances tested here. Inequalities from the Stable Set polytope improve the best known Linear Programming Relaxation (LPRs) bounds by about 1.6%, on average, for the hardest instances of the problem. Additionally, we indicate how formulation $${\mathcal {F}}_{xy}$$ F xy can be more effectively used in Branch-and-cut (BC) algorithms, by reducing the number of variables explicitly enforced to be integer constrained and by eliminating constraints that do not change the quality of its LPR bounds. Extensive computational experiments conducted here suggest that the combination of the ideas above allows us to redefine the best performing $$\alpha $$ α -MSTP algorithms, for almost the entire spectrum of $$\alpha $$ α values, the exception being the easy instances, those with $$\alpha \ge \frac{2\pi }{3}$$ α ≥ 2 π 3 . In particular, for the hardest ones (corresponding to $$\alpha \in \{\frac{\pi }{2}, \frac{\pi }{3},\frac{2\pi }{5}\}$$ α ∈ { π 2 , π 3 , 2 π 5 } ) that could be solved to proven optimality, the best BC algorithm suggested here improves on average CPU times by factors of up to 5, on average.

Keywords: Combinatorial optimization; Angular constrained spanning trees; Stable set polytope; Branch-and-cut algorithms (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-021-00835-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:44:y:2022:i:1:d:10.1007_s10878-021-00835-w

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-021-00835-w

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().