Rutcor Research Report Improved bounds on the existence of a feasible flow in a stochastic transportation network Merve Unuvar a Ozlem Cavus András Prékopa c b RRR 23-2012, June 2012 RUTCOR Rutgers Center for Operations Research Rutgers University 640 Bartholomew Road Piscataway, New Jersey 08854-8003 Telephone: 732-445-3804 Telefax: 732-445-5472 Email: [email protected] http://rutcor.rutgers.edu/∼rrr a RUTCOR, Rutgers University, 640 Bartholomew Road, Piscataway, NJ, 08854-8003; [email protected] b RUTCOR, Rutgers University, 640 Bartholomew Road, Piscataway, NJ, 08854-8003; [email protected] c RUTCOR, Rutgers University, 640 Bartholomew Road, Piscataway, NJ, 08854-8003; [email protected] Rutcor Research Report RRR 23-2012, June 2012 Improved bounds on the existence of a feasible flow in a stochastic transportation network Merve Unuvar Ozlem Cavus András Prékopa Abstract. A. Prékopa and E. Boros published a paper “On the Existence of a Feasible Flow in a Stochastic Transportation Network” that appeared in Operations Research 39(1991), 119-129. In that paper the authors gave a powerful technique to evaluate transportation system reliability. At the nodes production takes place and the products are shipped on the arcs. Interconnected power systems are the primary examples for the application of the method. Reliability means that in case of efficiency in the electricity production, the power system can assist each other so that all demand can be met. The mentioned reliability calculation method uses probability bounding techniques developed by the same authors. However, there are some other bounds based on individual probability calculations which can be used to compute more efficient bounds. The proposed project aims to improve on the reliability calculation method, by using other and more recent probability bounding techniques. These improved bounds; hunter bound and cherry tree bounds are calculated based on individual probabilities. Acknowledgements: The first two authors were supported by DIMACS Graduate Student Award, Summer 2008. Page 2 1 RRR 23-2012 Introduction A stochastic transportation network consists of real valued random variables which are associated with determining the demand at each node. (The value of the demand may be positive negative or zero depending on the function definition of demand. The absolute value of a negative valued demand becomes the supply amount) In addition to random demand and supply variables, the network may contain random arc capacities. At designated time, each node in the network randomly becomes demand, supply or neither of them depending on its value. The supply nodes must assist the demand nodes through a flow that is to be found given the realized values of the random variables. The interpretation of demand and arc functions depend on the application of stochastic transportation network. For the power engineering applications, power generating capacities at the nodes and the maximum transmission capacities on arcs are the deterministic variables that are used in connection with demand and arc capacity functions. The performance measure of the network, which is usually the probability of a feasible flow, depends on these variables. The reliability function involves the calculation of joint probability distribution function hence its numerical evaluation while solving for least cost network design objective is not easy in many cases. In order to handle this difficulty, Prékopa and Boros [7] proposed a method to analyze networks from the reliability point of view and suggest that this method be used interactively when solving a design problem. In their paper, reliability analysis is split in two separate parts. First, they eliminate all redundant constraints among those that jointly represent the necessary and sufficient conditions for the existence of a feasible flow and are obtained by enumerating all cuts in the network. This elimination uses some lower and upper bounds only, assumed to be known, regarding the demand and capacity functions; hence, the result is the same no matter if the demand and capacity values vary deterministically or randomly between their bounds. Second, in order to find the probability of the existence of a feasible flow, they applied the recently developed probability approximation technique of [5], [6]. In this paper, we are going to evaluate some other bounds for the stochastic transportation networks. One of the bound is Hunter’s upper bound. The calculation of this bound was already known when the paper was first published however is not included in the paper so we decided to first calculate Hunter’s upper bound. Secondly, since the publication of the transportation system reliability calculation paper further, more efficient bounding techniques such as cherry tree bounds, have been created, we try to make improvements on the reliability calculation method, by using this more recent probability bounding technique. In the first section, since we have used the same notation in Prékopa and Boros [7] paper, we similarly first introduce you the preliminaries. Although we did not work on the elimination procedure, we detected some redundant constraints and eliminated them. Afterwards, we picked the most complicated example (see Figure 1) in the paper and tried to find new bounds for it. We calculated the Hunter’s upper bound and cherry tree bounds and then compared the results with the one Prékopa and Boros [7] found. RRR 23-2012 2 Page 3 Preliminaries In this section, we will briefly give some basic definitions related with networks. We will closely follow the notation and presentation of Prékopa and Boros [7]. The reader is referred to [7] and [2] for details. We consider a network G = (N, A) with N and A ⊂ N × N representing the set of nodes and and the set of arcs, respectively. Similar to Prékopa and Boros [7], we assume that if the arc (i, j) is an element of set A, then (j, i) ∈ A. We show the arc capacities by y(i, j) ∈ R, (i, j) ∈ A, flow on arcs by f (i, j) ∈ R, (i, j) ∈ A, and demand at nodes by d(i) ∈ R, i ∈ N . If d(i) < 0, then node i is called a supply node. Let B and C be subsets of N . The demand at set B is given by d(B) = X d(i). i∈B We show the flow from set B to set C by f (B, C) = X f (i, j), i∈B,j∈C and the corresponding capacity by y(B, C) = X y(i, j). i∈B,j∈C We say the flow f (i, j) on an arc (i, j) is admissible if f (i, j) ≤ y(i, j) and f (i, j)+f (j, i) = 0. If there exists a flow f satisfying the following condition f (N, i) ≥ d(i) for every i ∈ N, (1) the demand function d will be called to be feasible. Gale [2] and Hoffman [3] showed that if the following theorem holds, then there exists an admissible flow satisfying the relation (1). Theorem 2.1. (Gale and Hoffman). Let S ⊆ N and S̄ = N \S, then the demand d(i), i ∈ N is feasible if and only if the following relation holds for every set S d(S) ≤ y(S̄, S). In this study, we use some recent bounding techniques for bounding the probability of demand being feasible P (d(S) ≤ y(S̄, S) for any S ⊆ N ). (2) RRR 23-2012 Page 4 Figure 1: Fifteen node example 3 Elimination of Redundant Inequalities and Constructing Superareas In this section, we have written noneliminated constraints for the Figure 1 according to Table VII in Prékopa and Boros [7]. After carefully observing each inequality, in addition to elimination of Prékopa and Boros [7], we realized that the second constraint (that can be written from the Table VII) is redundant. Because d(11, 12) ≤ 5450 is always satisfied with probability 1. (Probability calculations can be made from Table 1 such as: d(11) + d(12) is at most 2020 + 3375 = 5395 which is always less than 5425 so the second constraint is RRR 23-2012 Page 5 Table 1: Characteristics vectors of noneliminated inequalities for 15-node network Number 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 3 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 4 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 5 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 6 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 7 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 8 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 9 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 10 1 1 1 1 1 0 0 0 0 0 0 0 1 1 0 11 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 12 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 13 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 redundant.) d(15) ≤ 3500 d(11, 12) ≤ 5450 d(10, 11, 12 ≤ 5425 d(7, 8, 9, 19, 11, 12, 15) ≤ 6000 d(3, 4, 5, 13, 14, 15) ≤ 6500 d(3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15) ≤ 1500 d(1, 2) ≤ 1500 d(1, 2, 3, 13, 14, 15) ≤ 8350 d(1, 2, 3, 4, 5, 13) ≤ 6150 d(1, 2, 3, 4, 5, 13, 14) ≤ 5500 d(1, 2, 3, 4, 5, 13, 14, 15) ≤ 5000 d(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13) ≤ 4150 d(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15) ≤ 0 A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 After eliminating the second row of Table 1 (because of the redundancy) we are now ready to create the superares. In order to see which nodes can be combined as superareas, we can RRR 23-2012 Page 6 Table 2: Characteristic Vectors of super areas ((1,2), (3,13), (4,5), (7,8,9),(10),(11,12),(14),(15).) (Second row eliminated because of redundancy) (6), (1,2) (3,13) (4,5) (6) (7,8,9) (10) (11,12) (14) (15) 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 1 0 1 1 0 0 0 0 1 1 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 just check the columns of the Table 1. For instance, the first and second column of the Table 1 is same, therefore we can combine those two nodes as one node (1, 2). In the same way, we can also combine : (1, 2), (3, 13), (4, 5), (6), (7, 8, 9), (10), (11, 12), (14), (15). As a result, we have Table 2 for Characteristic Vectors of Noneliminated Inequalities. After elimination and construction of superareas, the new constraint set becomes as follows: d(15) ≤ 3500 d(10, 11, 12) ≤ 5425 d(7, 8, 9, 19, 11, 12, 15) ≤ 6000 d(3, 4, 5, 13, 14, 15) ≤ 6500 d(3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15) ≤ 1500 d(1, 2) ≤ 1500 d(1, 2, 3, 13, 14, 15) ≤ 8350 d(1, 2, 3, 4, 5, 13) ≤ 6150 d(1, 2, 3, 4, 5, 13, 14) ≤ 5500 d(1, 2, 3, 4, 5, 13, 14, 15) ≤ 5000 d(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13) ≤ 4150 d(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15) ≤ 0 A1 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 RRR 23-2012 Page 7 S¯1 = 0.145739011 S¯2 = 0.026857925 S¯3 = 0.017572 Table 3: Lower and Upper Bounds on the Probability of the Feasible Flow in the 15-Node Network Using the First m Binomial Moments for m = 1, 2, 3 m Lower Upper 1 0.8543 0.9879 2 0.8587 0.8811 3 0.8679 0.8767 3.1 Hunter’s Upper Bound Let E1 , E2 , E3 , . . . , Em be events in a probability space. Pi = P (Ei ), i = 1, . . . , m Pij = P (Ei , Ej ) i 6= j Create a graph with m nodes connect all node pairs by arcs (complete graph) and assign Pij as weight of the arc connecting i, j. Hunter’s upper bound (Hunter, 1976), P (E1 ∪ E2 ∪ · · · ∪ Em ) ≤ m X i=1 Pi − X Pij i,j∈T Where T is any spanning tree in the graph. The best bound is obtained if T = T ∗ , the heaviest spanning tree. In our example, the complementary probabilities of the events are taken into account in order to find the spanning trees out. The heaviest spanning tree that we have used is formed by the edges given in Table 4. The edge probabilities are also provided in the same table. Table 4: Spanning tree and edge probabilities (1 -7) (7 - 11) (7 - 9) (5 - 11) (11 - 13) (9 - 10) (3 - 7) (6 - 13) (1 - 4) (8 - 11) (12 - 13) 0.00350 0.00204 0.00178 0.00159 0.00096 0.00083 0.00077 0.00067 0.00053 0.00035 0.00009 When we apply the above formula to our case with the heaviest spanning tree, the bound is 0.8673751. RRR 23-2012 Page 8 3.2 Cheery Tree Bound First let us introduce the concept of cherry tree. A third order upper bound on the probability of the union of a finite number of events, is presented by means of graphs called cherry trees. These are graphs that we construct recursively in such a way that every time we pick a new vertex, we connect it with two already existing vertices. If the latters are always adjacent, we call this a t-cherry tree. A cherry tree has a weight that provides us with the upper bound on the union. A cherry tree bound can be identified as a feasible solution to the dual of the Boolean probability bounding problem. Moreover, a t-cherry tree bound can be identified as the objective function value of the dual vector corresponding to a dual feasible basis in the Boolean problem. This enables us to make an improvement on the bound algorithmically, if we use the dual method of linear programming. First we will recall the definition of a cherry tree: Definition 3.1. (Bukszár, Prékopa [1]) We define a cherry tree recursively in the following manner: (i) An adjacent pair of vertices constitutes the only cherry tree that has exactly two vertices. (ii) From a cherry tree we can obtain another cherry tree by adding a new vertex and two new edges, connecting the new vertex with two already existing vertices. These two edges constitute a cherry. (iii) If V is the set of vertices, ξ the set of edges and ε the set of cherries obtained that way then we call the triple ∆ = (V, ξ, ε) a cherry tree. Theorem 3.1. Bukszár and Prékopa [1] For any cherry tree ∆ = (V, ξ, ε) with V = 1, . . . , n we have Pn P (Ai ) − w(∆) = S1 − w(∆) where P P w(∆) = {i,j}∈ξ P (Ai ∩ Aj ) − (i,j,k)∈ξ P (Ai ∩ Aj ∩ Ak ) P (A1 ∪ · · · ∪ An ) ≤ i=1 (3) Proof of the Theorem (3.1) can be found in Bukszár and Prékopa [1]. The cherries that we have found and their corresponding probabilities are provided in Table 5. Table 5: Cherries and corresponding probabilities (7-11-9) (9-10-11) (7-1-11) (1-5-11) (7-13-11) (11-6-13) (1-8-11) (6-12-13) (6-3-13) (6-4-13) 0.000919 0.000831 0.000558 0.000703 0.000456 0.000369 0.000195 5.25E-05 0.000158 0.000115 By using those cherries, we have calculated a Cherry Tree Bound as 0.868780501. RRR 23-2012 Page 9 References [1] Bukszár J., Prékopa A. (2001) Probability Bounds with Cherry Trees, Mathematics of Operations Research, 26, 174-192. [2] Gale, D. (1957) A Theorem on Flows in Networks, Pacific J. Math., 7, 1073-1082. [3] Hoffman, A. J. (1960) Some Recent Applications of the Theory of Linear Inequalities to Extremal Combinatorial Analysis, In Proceedings of Syposia in Applied Mathematics, Vol. X. Combinatorial Analysis. Americal Mathematical Society, 113-127. [4] Hunter D. (1976) An Upper bound for the Probability of a Union, Applied Probability Trust, 13, 597-603. [5] Prékopa A. (1988) Boole-Bonferroni Inequalities and Linear Programming, Operations Research 36 145–162. [6] Prékopa A. (1990) Sharp Bounds on Probabilities Using Linear Programming, Operations Research 38 227–239. [7] Prékopa, A. and E. Boros. (1991) On the Existence of a Feasible Flow in a Stochastic Transportation Network, Operations Research 39, 119-129. [8] Prékopa, A. and L. Gao. (2005) Bounding the Probability of the Union of Events by the Use of Aggregation and Disaggregation in Linear Programs. Discrete Applied Math 145, 444-454.