Two Uncertain Programming Models for Inverse Minimum Spanning Tree Problem

Abstract

An inverse minimum spanning tree problem makes the least modification on the edge weights such that a predetermined spanning tree is a minimum spanning tree with respect to the new edge weights. In this paper, the concept of uncertain <TEX>${\alpha}$</TEX>-minimum spanning tree is initiated for minimum spanning tree problem with uncertain edge weights. Using different decision criteria, two uncertain programming models are presented to formulate a specific inverse minimum spanning tree problem with uncertain edge weights involving a sum-type model and a minimax-type model. By means of the operational law of independent uncertain variables, the two uncertain programming models are transformed to their equivalent deterministic models which can be solved by classic optimization methods. Finally, some numerical examples on a traffic network reconstruction problem are put forward to illustrate the effectiveness of the proposed models.