|
Some models for inverse minimum spanning tree problemwith uncertain edge weights |
|---|---|
| รหัสดีโอไอ | |
| Creator | 1. Sagarika Biswal 2. Ganesh Ghorai |
| Title | Some models for inverse minimum spanning tree problemwith uncertain edge weights |
| Publisher | Research and Development Office, Prince of Songkla University |
| Publication Year | 2565 |
| Journal Title | Songklanakarin Journal of Science an Technology (SJST) |
| Journal Vol. | 44 |
| Journal No. | 5 |
| Page no. | 1353-1364 |
| Keyword | minimum spanning tree, uncertain minimum spanning tree, rough minimum spanning tree, inverse optimization, uncertainty theory |
| URL Website | https://sjst.psu.ac.th/ |
| ISSN | 0125-3395 |
| Abstract | The inverse minimum spanning tree (IMST) problem is an inverse optimization problem in which one makes the leastmodification to the edge weights of a predetermined spanning tree, to make it the minimum spanning tree with respect to newedge weights. For a deterministic environment, the problem has been extensively studied. In an uncertain environment, theproblem has been studied previously using stochastic edge weights or fuzzy edge weights. However, in the absence of enoughdata, approximation of a random variable is not possible. Further, the unobservable nature of edge weights means that assignmentof fuzzy weights is also not possible. In this situation, the assignment of edge weights is done based on belief degree of someexperts in the field. To deal with the problem of belief degree, the uncertainty theory is mostly suited. In this paper, two specificmodels 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. Themodels are converted to their equivalent deterministic models, which are solved by some standard optimization method. Anumerical example is given to illustrate the model and its solution. |
