  Due to its broad applications in practice, the minimum spanning tree problem
and its all kinds of variations have been studied extensively during the last
decades, for which a host of efficient exact and heuristic algorithms have been
proposed. Meanwhile, motivated by realistic applications, the minimum spanning
tree problem in stochastic network has attracted considerable attention of
researchers, with respect to which stochastic and robust spanning tree models
and related algorithms have been continuingly developed. However, all of them
would be either too restricted by the types of the edge weight random variables
or computationally intractable, especially in large-scale networks. In this
paper, we introduce a target-based distributionally robust optimization
framework to solve the minimum spanning tree problem in stochastic graphs where
the probability distribution function of the edge weight is unknown but some
statistical information could be utilized to prevent the optimal solution from
being too conservative. We propose two exact algorithms to solve it, based on
Benders decomposition framework and a modified classical greedy algorithm of
MST problem (Prim algorithm),respectively. Compared with the NP-hard stochastic
and robust spanning tree problems,The proposed target-based distributionally
robust minimum spanning tree problem enjoys more satisfactory algorithmic
aspect and robustness, when faced with uncertainty in input data.
