Journal Search Engine
Search Advanced Search Adode Reader(link)
Download PDF Export Citaion korean bibliography PMC previewer
ISSN : 1598-7248 (Print)
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

Jian Zhou*, Xiang Zhang, Qina Wang
School of Management, Shanghai University, Shanghai, China
Received: August 15, 2012, Revised: December 13, 2012, Accepted: March 5, 2013

Abstract

An inverse minimum spanning tree problem makes the least modification on the edge weights such that a predeterminedspanning tree is a minimum spanning tree with respect to the new edge weights. In this paper, the concept ofuncertain α-minimum spanning tree is initiated for minimum spanning tree problem with uncertain edge weights. Usingdifferent decision criteria, two uncertain programming models are presented to formulate a specific inverse minimumspanning tree problem with uncertain edge weights involving a sum-type model and a minimax-type model. Bymeans of the operational law of independent uncertain variables, the two uncertain programming models are transformedto their equivalent deterministic models which can be solved by classic optimization methods. Finally, somenumerical examples on a traffic network reconstruction problem are put forward to illustrate the effectiveness of theproposed models.

12-1-02_9-15_ Xiang Zhang, Qina Wang, Jian Zhou.pdf546.7KB

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, Lk, Mk) be uncertainty spaces for k = 1, 2, …. The product uncertain measure M is an uncertain measure satisfying 

 

where Λk are arbitrarily chosen events from Lk 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 B1, B2, …, Bn of real numbers. 

Theorem 1 (Liu, 2010). Let ξ12, …, ξn be independent uncertain variables with regular uncertainty distributions Φ1, Φ2, …, Φn, respectively. If the function f (x1, x2, …, xn) is strictly increasing with respect to x1, x2, …, xk and strictly decreasing with respect to xk+1, xk+2, …, xn 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 xi, i∈E{1, 2, …, m}, a spanning tree T0 is said to be a minimum spanning tree if 

 

holds for any spanning tree T. 

In a classic IMST problem, a predetermined spannng tree T0 is given. The objective of IMST problem is to find some new edge weights such that T0 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 T0 as tree edges, and the edges not in T0 as non-tree edges. Hence the set of all the non-tree edges is E \ T0. In the spanning tree T0, 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 Pj. An example of classic IMST problem with 6 vertices and 10 edges is shown in Figure 2, where ci and xi denote the original and new weights on edge i, and the solid line represents a given spanning tree T0. The set of non-tree edges is E \ T0 = {6, 7, 8, 9, 10}, and the tree path of non-tree edge BD is AB-AE-DE, i.e., P9 = {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). T0 is a minimum spanning tree with respect to the edge weights if and only if 

 

where E \ T0 is the set of non-tree edges, and Pj is the tree path of edge j. 

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

 

where ci and xi 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};
T0 : a predetermined spanning tree of G;
ci : the original edge weights i, i∈E;
xi : decision variables representing the new edge weights i, i∈E;
ξi(xi) : the uncertain edge weights with respect to xi, i ∈E. 

For our purpose, we assume that xi ≥ ci, 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 T0 is a minimum spanning tree with respect to the uncertain edge weights ξi(xi), 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 T0 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. T0 is an uncertain α -minimum spanning tree with respect to the uncertain edge weights if and
only if 

 

where E \ T0 is the set of non-tree edges, and Pj 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 xi, 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 xi

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 T0 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 T0. There are three weights on each road, where ci and xi 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 , xi, i.e., ξii(xi) = L(200 − xi, 200 − xi + ai) (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 \ T0 ={6, 7, 8, 9, 10}, Pj 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(xi, 0.8) = 200 + 0.8ai − xi, Φj−1(xj, 0.2) = 200 + 0.2aj − xj according to (2), it follows that Φi−1(xi, 0.8) − Φj−1(xj, 0.2) = −xi + xj +0.8ai − 0.2aj.

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 x1* and x2* are optimal solutions of model (16), while only x1* 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

1.Ahuja, R. K., Magnanti, T. L., and Orlin, J. B. (1993), Network Flows: Theory, Algorithms, and Applications, Prentice Hall, Englewood Cliffs, NJ.
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 l1 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.