Target-based distributionally robust minimum spanning tree problem
针对边权重分布未知的随机图，提出一种基于目标的分佈稳健最小生成树模型，利用部分统计信息降低保守性，并开发了三种精确算法，在大规模网络中表现出更好的鲁棒性和效率。
• 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.