ISSN : 2234-6473 (Online)

**Industrial Engineering & Management Systems Vol.12 No.1 pp.9-15**

DOI : https://doi.org/10.7232/iems.2013.12.1.009

# Two Uncertain Programming Models for Inverse Minimum Spanning Tree Problem

### Abstract

- 1. INTRODUCTION
- 2. PRELIMINARIES
- 3. UNCERTAIN INVERSE MINIMUM SPANNING TREE PROBLEM
- 3.1 Classic IMST Problem
- 3.2 Application Backgrounds
- 3.3 Notations and Problem Description
- 3.4 Uncertain α-minimum Spanning Tree
- 4. UNCERTAIN PROGRAMMING MODELS
- 4.1 Uncertain Sum-Type Model
- 4.2 Uncertain Minimax-Type Model
- 5. COMPUTATIONAL EXAMPLES
- 6. CONCLUSION
- ACKNOWLEDGMENTS

### 1. INTRODUCTION

The inverse optimization problem is a subject extensively studied in the context of tomographic studies, seismic wave propagation, and in a wide range of statistical inference with prior problems. The inverse minimum spanning tree (IMST) problem is a type of inverse optimization problems. In an IMST problem, a connected graph with edge weights is considered. The objective of IMST problem is to modify the weights so that a predetermined spanning tree is a minimum spanning tree with respect to the new weights, and simultaneously the total modification of weights is a minimum.

The IMST problem was first studied by Zhang et al. (1996). Following that, much research work has been done onthe IMST problem since many applications can be transformed to this problem (Farago et al., 2003; Guan and Zhang, 2007; Wang et al., 2006; Yang and Zhang, 2007). And many efficient algorithms have been developed for solving the classic IMST problems and their derivatives (Ahuja and Orlin, 2000; He et al., 2005; Zhang et al., 2006). In view of the nondeterminacy of some parameters in applications, some endeavor was done to deal with IMST problems with indeterminate information in the literatures. For example, Zhang and Zhou (2006) considered the IMST problem when the edge weights were assumed to be stochastic variables, and stochastic programming models together with hybrid intelligent algorithms were presented for IMST problems.

In practice, however, it is not appropriate to set the edge weights as random numbers in some cases due to a lack of observed data (Peng and Li, 2011; Zhou and Peng, 2011). Hence, we adopt the uncertainty theory, a branch of axiomatic mathematics for modeling human uncertainty founded by Liu (2007), to handle this problem. In this paper, a specific IMST problem is discussed under the assumption of uncertain edge weights. This paper proposes a new concept of uncertain α-minimum spanning tree and develops two uncertain programming models to formulate this problem according to different decision criteria. In this paper, the IMST problem with uncertain edge weights is referred to as an uncertain inverse minimum spanning tree (UIMST) problem for convenience.

The rest of this paper is organized as follows. Section 2 briefly reviews the preliminary concepts of uncertainty theory. Section 3 introduces the classic IMST problem and the mathematical description of UIMST problem, and then proposes a concept of uncertain α- minimum spanning tree. In Section 4, two uncertain programming models are given based on different decision objectives. Following that, Section 5 presents the numerical examples in terms of the two uncertain models. Finally, conclusions are drawn in Section 6.

### 2. PRELIMINARIES

Uncertainty theory provides a new approach to deal with indeterminacy factors when there is a lack of observed data (Liu, 2007, 2010). Nowadays, uncertainty theory has become a branch of axiomatic mathematics for modeling human uncertainty, widely applied in many research areas (Chen, 2011; Li and Peng, 2012; Sheng and Yao, 2012; Xu and Zhu, 2012). This section is intended to review some basic concepts in uncertainty theory which will be used to establish uncertain programming models for the UIMST problem.

Definition 1 (Liu, 2007). Let L be a σ -algebra on a nonempty set Γ. A set function M: L→[0, 1] is called an uncertain measure if it satisfies the following axioms:

**Axiom 1 **(Normality Axiom). M{L} =1 for the universal set Γ;**Axiom 2** (Duality Axiom). M{Λ}+ M{Λ^{c}} = 1 for any event Λ;**Axiom 3** (Subadditivity Axiom). For every countable sequence of events Λ_{1}, Λ_{2}, …, we have

The triplet (Γ, L, M) is called an uncertainty space. Besides, the product uncertain measure on the product σ -algebra was defined by Liu (2009) via the following product axiom:

**Axiom 4** (Product Axiom). Let (Γ_{k}, L_{k}, M_{k}) be uncertainty spaces for k = 1, 2, …. The product uncertain measure M is an uncertain measure satisfying

where Λ_{k} are arbitrarily chosen events from L_{k} for k = 1, 2, …, respectively.

An uncertain variable ξ is essentially a measurable function from an uncertainty space to the set of real numbers. In order to describe an uncertain variable in practice, Liu (2007) defined a concept of uncertainty distribution as follows.

**Definition 2** (Liu, 2007). Let ξ be an uncertain variable. Then, its uncertainty distribution is defined by

for any real number x.

Furthermore, Peng and Iwamura (2010) showed that a function M: R→[0, 1] is an uncertainty distribution if and only if it is a monotone increasing function except Φ(x) ≡ 0 and Φ(x) ≡ 1.

For instance, an uncertain variable ξ is called linear if it has a linear uncertainty distribution (Figure 1),

denoted by ξ : L(a, b), where a and b are real numbers with a < b.

**Figure 1.** Linear uncertainty distribution.

An uncertainty distribution Φ is said to be regular if its inverse function Φ^{−1}(α ) exists and is unique for each α ∈(0, 1). It is clear that a linear uncertainty distribution L(a, b) is regular, and its inverse uncertainty distribution is

The inverse uncertainty distribution plays an important role in the operations of independent uncertain variables.

**Definition 3** (Liu, 2009). The uncertain variables ξ_{1}, ξ_{2}, …, ξ_{n} are said to be independent if

for any Borel sets B_{1}, B_{2}, …, B_{n} of real numbers.

Theorem 1 (Liu, 2010). Let ξ_{1} ,ξ_{2}, …, ξ_{n} be independent uncertain variables with regular uncertainty distributions Φ_{1}, Φ_{2}, …, Φ_{n}, respectively. If the function f (x_{1}, x_{2}, …, x_{n}) is strictly increasing with respect to x_{1}, x_{2}, …, x_{k} and strictly decreasing with respect to x_{k+1}, x_{k+2}, …, x_{n} then

is an uncertain variable with inverse uncertainty distribution

### 3. UNCERTAIN INVERSE MINIMUM SPANNING TREE PROBLEM

In this section, a classic concept of minimum spanning tree as well as a path optimality condition is reviewed briefly, and then an UIMST problem is initialized by introducing its application backgrounds and mathematical description. Finally, a new concept of uncertain α -minimum spanning tree is presented.

#### 3.1 Classic IMST Problem

**Definition 4** (Minimum Spanning Tree). Given a connected graph G = (V, E) with edge weights x_{i}, i∈E{1, 2, …, m}, a spanning tree T^{0} is said to be a minimum spanning tree if

holds for any spanning tree T.

In a classic IMST problem, a predetermined spannng tree T^{0} is given. The objective of IMST problem is to find some new edge weights such that T^{0} is a minium spanning tree with respect to the new edge weights and accordingly the modification of edge weights is a minimum.

In order to provide the mathematical description of IMST problem, some notions are proposed as follows. Firstly, we refer to the edges in the given spanning tree T^{0} as tree edges, and the edges not in T^{0} as non-tree edges. Hence the set of all the non-tree edges is E \ T^{0}. In the spanning tree T^{0}, there is a unique path between the two vertices of any non-tree edge j, referred to as tree path of edge j and denoted by P_{j}. An example of classic IMST problem with 6 vertices and 10 edges is shown in Figure 2, where c_{i} and x_{i} denote the original and new weights on edge i, and the solid line represents a given spanning tree T^{0}. The set of non-tree edges is E \ T^{0} = {6, 7, 8, 9, 10}, and the tree path of non-tree edge BD is AB-AE-DE, i.e., P_{9} = {1, 3, 5}.

**Figure 2.** An example of inverse minimum spanning tree problem.

Moreover, Ahuja et al. (1993) proved an equivalent condition of minimum spanning tree, called a path optimality condition as follows.

**Theorem 2** (Ahuja et al., 1993). T^{0} is a minimum spanning tree with respect to the edge weights if and only if

where E \ T^{0} is the set of non-tree edges, and P_{j} is the tree path of edge j.

According to Theorem 2, the classic IMST problem can be formulated as the following model,

where c_{i} and x_{i} are the original and new weights of edge i, i∈E, respectively. Note that the objective function can be replaced with some other objective functions if necessary (Sokkalingam et al., 1999).

#### 3.2 Application Backgrounds

Many reconstruction problems in practice can be transformed to uncertain problems. Let us consider a LAN reconstruction problem as follows.

Much research work shows that the spanning tree structure is the best topology for telecommunication network designs (Kershenbaum, 1993), especially in computer network systems. LANs are commonly used as a communication infrastructure that meets the demands of users in a local environment. These computer networks typically consist of several LAN segments connected via bridges.

Suppose that there is an old LAN, in which several service centers are interconnected via bridges. Because of the tremendous network congestion, the bandwidths on bridges must be modified. The decision-maker hopes that a predetermined spanning tree becomes a minimum spanning tree with respect to the traveling time (which means high net-speed) between the main service centers. Also the total bandwidth modification should be minimized so as to diminish the cost of reconstruction.

Since the traveling times as well as the net speeds are related to bandwidths, it is natural to describe the traveling time on a bridge as an uncertain number instead of a deterministic one with respect to bandwidths of bridges when there are no former statistical data. This is a typical inverse spanning tree problem with uncertain weights, i.e., a UIST problem.

#### 3.3 Notations and Problem Description

In this paper, a specific IMST problem with uncertain edge weights is investigated. In order to provide a mathematical description for this problem, the following notations are used:

G = (V, E) : a connected graph with set of n vertices V and edge set E = {1, 2, …, m};

T^{0} : a predetermined spanning tree of G;

c_{i} : the original edge weights i, i∈E;

x_{i} : decision variables representing the new edge weights i, i∈E;

ξ_{i}(x_{i}) : the uncertain edge weights with respect to x_{i}, i ∈E.

For our purpose, we assume that x_{i} ≥ c_{i}, i∈E which is practical in many situations. For instance, in a traffic system reconstruction problem, the roads are often required to be broadened instead of being narrowed in order for accommodating the increasing traffic flow. Hence the objective of UIMST problem here is to find a new edge weight vector x to minimize the modification and simultaneously T^{0} is a minimum spanning tree with respect to the uncertain edge weights ξ_{i}(x_{i}), i∈E.

#### 3.4 Uncertain α-minimum Spanning Tree

In a UIMST problem, Definition 4 becomes powerless due to the uncertainty of edge weights ξ_{i}. Therefore, before modeling the UIMST problem, a minimum spanning tree with respect to uncertain weights must be defined first. In this section, by using the uncertainty measure (see Section 2), a new concept of uncertain α - minimum spanning tree is recommended as follows.

**Definition 5** (Uncertain α -Minimum Spanning Tree). Given a connected graph G = (V, E) with uncertain edge weights ξ_{i}, i∈E and a given confidence level α , a spanning tree T^{0} is said to be an uncertain α -minimum spanning tree if

holds for any spanning tree T.

Definition 5 implies that an uncertain α -minimum spanning tree has a chance not less than α of not having an uncertain weight larger than every other spanning tree, which is intuitively reasonable.

As introduced in Section 3.1, Theorem 2 is a necessary and sufficient condition of minimum spanning tree, which provides a useful approach for modeling an IMST problem. In the UIMST problem, a similar result can be obtained for uncertain α -minimum spanning tree by adopting only a tiny change as follows.

**Theorem 3.** T^{0} is an uncertain α -minimum spanning tree with respect to the uncertain edge weights if and

only if

where E \ T^{0} is the set of non-tree edges, and P_{j} is the tree path of edge j.

**Proof.** It follows directly from Theorem 2 and Definition 5. □

### 4. UNCERTAIN PROGRAMMING MODELS

Based on the concept of uncertain α -minimum spanning tree and Theorem 3, two uncertain programming models are built up for the UIMST problem in this section including an uncertain sum-type model and an uncertain minimax-type model. Furthermore, the operational law of independent uncertain variables, i.e., Theorem 1 in Section 2, is used to derive two equivalent deterministic models.

#### 4.1 Uncertain Sum-Type Model

Let us consider a traffic network reconstruction problem, where some roads should be broadened for some reasons. The decision-maker hopes that the predetermined spanning tree becomes an uncertain α -minimum spanning tree with respect to uncertain traveling times between some main traffic hubs, where α is provided as an appropriate safety margin by the decision-maker. And the total modification of road widths is also required to be minimized which means decreasing the cost of reconstruction. In this case, a so-called uncertain sumtype model can be obtained from Theorem 3 as follows,

where α is a predetermined confidence level. This model means to make the least modification on the deterministic edge weights x_{i}, i∈E, such that a given spanning tree becomes an uncertain α -minimum spanning tree with respect to the uncertain edge weights ξ_{i}, i∈E.

By the use of Theorem 1, it is easy to convert model (10) into the following crisp equivalent model,

where Φ_{i}^{−1} represent the inverse distributions of uncertain weights ξ_{i}, i =1, 2, …, m, which are related to the new edge weights x_{i}.

#### 4.2 Uncertain Minimax-Type Model

Sometimes, the decision-maker hopes to minimize the maximal one among all the modifications so as to keep a balance of cost during the system reconstruction. In order to meet this objective, an uncertain minimaxtype model can be established as follows,

Similarly, using the inverse uncertainty distributions Φ_{i}^{−1} of edge weights, i∈E, an equivalent deterministic

model can be obtained as follows,

The objective function of model (13) is to minimize the largest modification in all the edges provided that a given spanning tree T^{0} becomes an uncertain α - minimum spanning tree regarding the uncertain edge weights.

Until now, two uncertain models together with their equivalent deterministic models are presented for the UIMST problem according to different decision objectives. We can see that models (11) and (13) have no difference with classical mathematical programming models when the inverse uncertainty distributions are known. Thus, we may solve them by classical optimization methods or intelligent algorithms.

### 5. COMPUTATIONAL EXAMPLES

In order to illustrate the effectiveness of the above two uncertain programming models, in this section, a traffic network reconstruction problem with 6 traffic hubs and 10 roads is considered (Figure 3), with the solid line representing the predetermined spanning tree T^{0}. There are three weights on each road, where c_{i} and x_{i} are the original and new widths of road i, respectively, and ξ_{i} denote the uncertain traveling times on road i, which are assumed to be linear uncertain variables only with respect to , x_{i}, i.e., ξ_{i} =ξ_{i}(x_{i}) = L(200 − x_{i}, 200 − x_{i} + a_{i}) (Table 1). Two uncertain models are given to formulate this problem and then solved by MATLAB (MathWorks, Natick, MA, USA).

**Figure 3.** Uncertain inverse minimum spanning tree problem for computational examples.

**Table 1.** Edge weights for UIMST problem in Figure 3

**Example 1.** Firstly, when the sum-type model (11) is used, the objective is to minimize the total modification of road widths with a given confidence level α = 0.8 so as to minimize the total cost of reconstruction, then the following uncertain programming model is obtained,

where the non-tree edge set E \ T^{0} ={6, 7, 8, 9, 10}, P_{j} is the tree path of non-tree edge j, and Φ_{i}^{−1} are inverse uncertainty distributions of ξ_{i}, i = 1, 2, …, 10. Since Φ_{i}^{−1}(x_{i}, 0.8) = 200 + 0.8a_{i} − x_{i}, Φ_{j}^{−1}(x_{j}, 0.2) = 200 + 0.2a_{j} − x_{j} according to (2), it follows that Φ_{i}^{−1}(x_{i}, 0.8) − Φ_{j}^{−1}(x_{j}, 0.2) = −x_{i }+ x_{j }+0.8a_{i} − 0.2a_{j}.

As a result, an equivalent formulation of model (14) can be gained as follows,

which is a linear programming model. Hence, we solve it by MATLAB 7.1 and get the optimal solution

and the minimum total modification on road widths is 210.

**Example 2.** Secondly, by the use of the minimax-type IMST model (13), we have the corresponding formulation for this problem like:

Similarly, with the help of MATLAB 7.1, model (16) is solved easily with the final solution

as well as the optimal objective value 140.

By making a further investigation on the experimental results, we have

which imply that both x_{1}^{*} and x_{2}^{*} are optimal solutions of model (16), while only x_{1}^{*} is the optimal solution of model (15). We can conclude from the computational results that model (16) has more than one optimal solution including that of model (15).

### 6. CONCLUSION

In this paper, the concept of uncertain α -minimum spanning tree is initiated for uncertain minimum spanning tree based on the uncertainty measure. After that, two uncertain programming models are presented to formulate the inverse minimum spanning tree problem with uncertain edge weights and then transformed to crisp equivalent models. Finally, the numerical examples on a traffic system reconstruction problem are put forward to illustrate the effectiveness of models proposed. The results of the computational examples led us to conclude that the uncertain minimax-type model has more than one optimal solution, and the optimal solution of uncertain sum-type model is also an optimal solution of uncertain minimax-type model. The multiple optimal solutions in Example 2 indicate that there are more than one plan for the decision-maker to choose for the reconstruction of the traffic network. As a complementary of this paper, a further study on the analysis of the solutions is needed. Some efficient algorithms to deal with the UIST problem should be also involved in the future work.

### ACKNOWLEDGMENTS

This work was supported in part by a grant from the Ministry of Education Funded Project for Humanities and Social Sciences Research (No. 12JDXF005), and the Shanghai Philosophy and Social Science Planning Project (No. 2012BGL006) and Innovation Program of Shanghai Municipal Education Commission (No. 13ZS065).

### Reference

2.Ahuja, R. K. and Orlin, J. B. (2000), A faster algorithm for the inverse spanning tree problem, Journal of Algorithms, 34(1), 177-193.

3.Chen, X. (2011), American option pricing formula for uncertain financial market, International Journal of Operations Research, 8(2), 27-32.

4.Farago, A., Szentesi, A., and Szviatovszki, B. (2003), Inverse optimization in high-speed networks, Discrete Applied Mathematics, 129(1), 83-98.

5.Guan, X. and Zhang, J. (2007), Inverse constrained bottleneck problems under weighted l

_{∞}norm, Computers and Operations Research, 34(11), 3243-3254.

6.He, Y., Zhang, B., and Yao, E. (2005), Weighted inverse minimum spanning tree problems under Hamming distance, Journal of Combinatorial Optimization, 9(1), 91-100.

7.Kershenbaum, A. (1993), Telecommunication Network Design Algorithms, McGraw-Hill, New York, NY.

8.Li, S. and Peng, J. (2012), A new approach to risk comparison via uncertain measure, Industrial Engineering & Management Systems, 11(2), 176-182.

9.Liu, B. (2007), Uncertainty Theory (2nd ed.), Springer- Verlag, Berlin.

10.Liu, B. (2009), Some research problems in uncertainty theory, Journal of Uncertain Systems, 3(1), 3-10.

11.Liu, B. (2010), Uncertainty Theory: A Branch of Mathematics for Modeling Human Uncertainty, Springer- Verlag, Berlin.

12.Peng, J. and Li, S. (2011), Spanning tree problem of uncertain network, Proceedings of the 3rd International Conference on Computer Design and Applications, Xi'an, Shaanxi, China.

13.Peng, Z. and Iwamura, K. (2010), A sufficient and necessary condition of uncertainty distribution, Journal of Interdisciplinary Mathematics, 13(3), 277-285.

14.Sheng, Y. and Yao K. (2012), Fixed charge transportation problem and its uncertain programming model, Industrial Engineering and Management Systems, 11(2), 183-187.

15.Sokkalingam, P. T., Ahuja, R. K., and Orlin, J. B. (1999), Solving inverse spanning tree problems through network flow techniques, Operations Research, 47(2), 291-298.

16.Wang, Q., Yang, X., and Zhang, J. (2006), A class of inverse dominant problems under weighted l

_{∞}norm and an improved complexity bound for Radzik's algorithm, Journal of Global Optimization, 34(4), 551-567.

17.Xu, X. and Zhu, Y. (2012), Uncertain bang-bang control for continuous time model, Cybernetics and Systems, 43(6), 515-527.

18.Yang, X. and Zhang, J. (2007), Some inverse min-max network problems under weighted l

_{1}and l

_{∞}norms with bound constraints on changes, Journal of Combinatorial Optimization, 13(2), 123-135.

19.Zhang, B., Zhang, J., and He, Y. (2006), Constrained inverse minimum spanning tree problems under the bottleneck-type Hamming distance, Journal of Global Optimization, 34(3), 467-474.

20.Zhang, J., Liu. Z., and Ma, Z. (1996), On the inverse problem of minimum spanning tree with partition constraints, Mathematical Methods of Operations Research, 44(2), 171-187.

21.Zhang, J. and Zhou, J. (2006), Models and hybrid algorithms for inverse minimum spanning tree problem with stochastic edge weights, World Journal of Modelling and Simulation, 2(5), 297-311.

22.Zhou, C. and Peng, J. (2011), Models and algorithm of maximum flow problem in uncertain network, Proceedings of the 3rd International Conference on- Artificial Intelligence and Computational Intelligence, Taiyuan, Shanxi, China, 101-109.