• Propose a target-based distributionally robust MST model for stochastic graphs. • Handle unknown edge-weight distributions using partial statistical information. • Develop three exact algorithms: a BD method and two modified Prim heuristics. • Achieve better robustness and efficiency than classical stochastic MST variants. • Scale effectively to large networks under significant edge-weight uncertainty. The minimum spanning tree (MST) problem and its variants have been extensively studied over the last few decades. Recently, more efforts have focused on stochastic networks where the edge weights are uncertain. Those efforts, however, are often overly restricted by the types of edge weight random variables or are computationally intractable, particularly in large-scale situations. To address these limitations, we propose a target-based distributionally robust optimization framework designed for the minimum spanning tree problem in stochastic graphs. In this framework, the probability distribution function of the edge weights is unknown, but we can utilize statistical information to reduce conservativeness. To seek optimal solutions, three exact algorithms, a Benders-decomposition-based (BD) method and two modified classical greedy algorithms of the MST problem (Prim algorithm), are constructed and tested. Compared with the traditional NP-hard stochastic and robust spanning tree problems, our proposed target-based distributionally robust minimum spanning tree (TDRMST) problem demonstrates superior performance in both algorithmic efficiency and robustness when dealing with input uncertainties.
Xu et al. (Sun,) studied this question.