Some models for inverse minimum spanning tree problem with uncertain edge weights

Abstract

The inverse minimum spanning tree (IMST) problem is an inverse optimization problem in which one makes the least modification to the edge weights of a predetermined spanning tree, to make it the minimum spanning tree with respect to new edge weights. For a deterministic environment, the problem has been extensively studied. In an uncertain environment, the problem has been studied previously using stochastic edge weights or fuzzy edge weights. However, in the absence of enough data, approximation of a random variable is not possible. Further, the unobservable nature of edge weights means that assignment of fuzzy weights is also not possible. In this situation, the assignment of edge weights is done based on belief degree of some experts in the field. To deal with the problem of belief degree, the uncertainty theory is mostly suited. In this paper, two specific models for inverse minimum spanning tree are initiated, taking rough variables and uncertain normal variables as edge weights. Based on the properties of uncertainty, two specific models are formulated for the inverse minimum spanning tree problem. The models are converted to their equivalent deterministic models, which are solved by some standard optimization method. A numerical example is given to illustrate the model and its solution.

Keywords

• minimum spanning tree
• uncertain minimum spanning tree
• rough minimum spanning tree
• inverse optimization
• uncertainty theory