An Improved Method for Sensitivity Analysis in Minimum Cost Flow Problem

An Improved Method for Sensitivity Analysis in Minimum Cost Flow Problem

Mahdalena, Herman Mawengkang

Graduate School of Mathematics, University of Sumatera Utara Campus USU, Medan, Indonesia – 20155

Abstract – The minimum cost flow problem is a combinatorial optimization model which can be modelled as a linear programming problem. This paper proposed a sensitivity analysis method for minimum cost flow problem, by exploring the bound constraint structure, such that maintains the structure of the optimal solution. We improved a sensitivity analysis method which is formerly applicable to a tree solution. the proposed method preserves solution of upper bounds at upper bounds and those of lower bounds at lower bounds.

Keywords:Sensitivity analysis, Network, Shortest path, Integer programming, Bound constraints.

1. INTRODUCTION

   Given a connected and directed graph G = (V,A), where V (v1, v2 ,…, vn ) is a set of nodes, and A is a set of directed arcs, the cost flow problem can be defined as follows. Let cij be the cost per unit flow for each arc (i, j) A. We assume that the flow cost varies linearly with the amount of flow. We also associate with each arc

   i, j A a capacity aij that denotes the maximum amount

   that can flow on the arc and lower bound lij that denotes the minimum amount that must flow m the arc. We associate with each node i A an integer value bi representing its

   All network problems are special cases of the minimum cost flow problem. Like the maximum flow problem, it considers flows in networks with capacities. Like the shortest path problem, it considers a cost for flow through an arc. Like the transportation problem, it allows multiple sources and destinations. Therefore, all of these problems can be seen as special cases of the minimum cost flow problem.

   As we can see that the model (P) is in the form of linear programming. The parameter values and assumption in the model are subject to change and error Therefore we would like to consider sensitivity analysis with respect to changes in the cost coefficients in problem ). Sensitivity analysis (SA), broadly defined, is the investigation of the potential changes and errors and their impacts on conclusions to be drawn from the model [1] The main idea of sensitivity analysis is to determine changes in the optimal solution of the problem resulting from changes in the data (supply/demand , capacity or cost of any arc) [10, 5, 2, 7, 9, 6, 4]. Traditionally, researchers have induced this sensitivity analysis using primal and dual simplex method [2]. There is, however a conceptual draw back to this approach. The simplex based approach maintains a basis free at every iteration and conduct sensitivity analysis by determining

   supply/demand. If bi 0 , node i is a supply node; if bi 0 node i is a demand node with a demand of bi ; and if bi 0 node i is a transhipment node. The decision variables m the minimum cost flow problem are arc flow

   which is represented by xij on i, j A . The model of the

   minimum cost flow problem (MCFP) can be expressed as follow.

   changes in the basis free precipitated by changes in the data.

   The basis in the simplex method is often degenerate and consequently changes in the basis tree are not necessarily translated into the changes in the optmal solution. The other thing is the relative inefficiency and complexity of the simplex methods (primal, dual, and other variations) for network models. Therefore, the simplex based approach does not give information about the changes in the solution as the data changes; instead it tells us about the changes in

   (1)

   min

   i, j A

   cij xij

   P

   the basis free [8, 3, 11, 2].

   The main idea for avoiding the short comings is to explore the bound structure given to the decision varibles

   x

   *

   ij

   xij . Let be an optimal solution of the minimum cost

   subject to

   flow problem. Regarding to the bound constraint

   (2)

   l x* a

   the arc set A is partitioned in to three

   where

   (3)

   (4)

   ij ij ij

   subsets as follows. Subset P contains (i, j) A , such that,

   l x* a

   , subset Q contains (i, j) A,

   such that,

   rerouting changes the optimal solution structure P,Q, R

   ij ij ij

   x l

   *

   ij ij

   x* a

   , and subset R contains (i, j) A, such that,

   due to a change in arc flow. Thus range of cost coefficients that maintains the optimal structure P,Q, R is the range

   right before the point where the flow of arc is changed.

   ij ij

   We call the triple P,Q, R

   as the optional solution

   Now suppose that the cost cij

   of an arc i, j increases

   structure.

   by cij cij . Then we want to know the range of , that

   x

   ij

   DEFINITION 1.1. Given an optimum solution * of the

   is e u , where u (e ) denote the amount of

   minimum cost flow problem. SA is to determined changes in the data that the optional solution structure remains

   maximum increasing (decreasing) flow that preserves the optimal solution structure P,Q, R. We first consider the

   unchanged.

   following network

   G V , A

   with multiple path

2. CHANGING THE COST COEFFICIENTS

   Here we consider SA with respect to changes in the cost

   x

   of

   ij

   coefficients. Suppose first that an optimal solution *

   P i, j from node i to node j. Suppose that the cost cij of an arc i, j is changed to cij . This changes the reduced

   x

   ij

   the MCFP is given. If the cost cij of an arc i, j changes to cij , then its corresponding optional solution * or the

   cost optimality conditions to restore the optimality condition of the arc, we must change the flow on arc i, j . We can

   both increase and decreare the flow in an arc i, j while

   optional solution structure P,Q, R may also change.

   knowing the bounds an arc flows. However, in an arc

   Hence, cost sensitivity analysis should determine changes in the cost of any arc such that the given optional solution

   i, h at its lower bound (i.e., xih lih ) we can only

   structure P,Q, R is unchanged. First, given a feasible

   increase the flow, and for flow on an arc i, m at its upper

   solution

   xij of the MCFP,

   xij is an optimum solution of the

   bound (i.e., xim uim ) we can only decrease the flow.

   MCFP if and only if for some set of node potentials w, the reduced costs and flow values satisfy the following complementary slackness optimality condition for every arc

   i, j A [8, 5, 2]

   Using the three concepts, we can find two paths

   and that

   can send the flow from node j. In our example, per unit cost to send one unit of flow along the path P1 i, j is

   (5)

   cih chj . If

   cih chjk cij , then the flow is sent along

   . (7)

   (6)

   P1 i, j . In this case the optimal structure P,Q, R may change. But, if the per unit cost to send one unit of flow

   Thus, given an optimum solution x* of the MCFP, SA

   along P1 i, j is greater than the per unit cost

   1

   cij , the

   ij

   with respect to changes in the cost coefficient in equivalent to determining cost range cij satisfying the following

   flow is not sent along P i, j . In this case since the flow

   along P1 i, j is not created, we can maintain the given

   conditions:

   optimal solution sructure P,Q, R in the interval of

   c e e . Similarly, 1 the per unit cost to send

   (8)

   (9)

   ij ih hj u

   one unit of flow along P2 i, j , is c c . If

   ki hj

   (10)

   c c c the flow will not be sent along P2

   and the

   Now, we consider a concept for the method of

   ki hj ij i, j

   structure P,Q, R can be preserved in the interval of

   calculating SA for cost coefficient. Given an optimal

   c e e . Here, let 1

   and 2

   be the upper

   solution

   x* of the MCFP, suppose that the cost

   cij

   of an

   ij ih hj u u

   ij

   arc i, j is changed to cij . If there is a path

   P i, j that

   bound of with respect to the path P1 i, j and

   can reroute the flow x*

   from node i to node j with less cost

   P2 i, j can preserve the given structure P,Q, R. Then

   ij 1 e c c

   and

   2 e e

   • e .

   than

   cij

   without violating any of the optimality conditions,

   u ij ih hj

   u ij hi hj

   x

   ij

   we should reroute the flow

   * along

   P i, j . This

   Consequently, u

   that maintains the optimal structure

   P,Q, R is restricted in value of min 1, 2 . In

   u u u

   u u u

   order to do there calculations easily consider a definition of transformed network.

   PROOF. If the directed path P i, j from node i to node j in

   G ' V , A' does not exist, there is no path P i, j that

   can send the flow from node i to node j in the network

   DEFINITION 2.1. The transformed network G ' V , A'

   G V , A. Therefore, even if the cost cij of an arc

   corresponding to a network G V , A of the MCFP is

   i, j increases infinitely, it is optimal to send the current

   defined as follows. We replace each arc i, j A with

   flow * along the arc i, j . So if the directed

   flow l x* u

   by two arcs i, j

   and j, i

   with the

   x

   ij

   ij ij ij

   path P i, j

   does not exist in

   G ' V , A', the

   u .

   cost cij cij and cji c ji respectively. We also replace

   Ultimately, if the shortest path exist in u we obtain a

   each arc i, j A with the flow

   *

   x u

   ij ij

   by arc j, i

   constant as the upper bound value u . But, if the shortest

   with the cost

   cji cji

   . Finally, we replace each arc

   path does not exist in

   G ' V , A'

   we obtain an infinite

   i, j A

   with the flow

   *

   x l

   ij ij

   by arc i, j

   with the

   value as the upper bound.

   cost cij cij .

   THEOREM 2.1. If

   G ' V , A'

   contains a shortest path

   Using the above transformed network G ' V , A', we can calculate by summing up the length of the

   from node i to node j and l is the length of the shortest path, then u l cij . If G ' V , A' contain no shortest

   u

   directed path P i, j from node i to node j and cij in

   path from node i to node j, then u .

   G ' V , A'. If there exists multiple directed paths

   PROOF. By lemma 2.1, G ' V , A'contains no negative

   P i, j form node i to node j, calculate u by summing

   cycle. Therefore if the shortest path exists in

   the minimum length of the directed path from node i to node

   G ' V , A', we can solve it. If the shortest

   j, calculate u

   by summing the minimum length of the

   G ' V , A', the directed paths

   P i, j

   does not exist

   directed path among various directed path and cij in G ' V , A'. Since among the various directed path the length of the directed path associated with the shortest path from node i to node j is the minimum, we need to calculate the length of the shortest path for the calculation of u [12].

   LEMMA 2.1. The transformed network G ' V , A'

   and by lemma 2.2.u . If there are multiple directed path P i, j from node i to node j, the u is obtained by summing the minimum length of the directed path among them, and cij in G ' V , A'. Let Ph i, j be the

   length of the both directed path among the multiple directed paths. Then l minPh i, j and u l cij . Next we

   contains a negative cycles.

   consider

   cij cij . Because per unit cost to send are

   PROOF. Assume the transformed network G ' V , A'

   unit of flow along the arc i, j is decreased by cij , more

   contains a negative cycle. This means that the network

   G V , A does not satisfy the optimality condition, and

   we can improve the current optimal solution with respect to this negative cycle. Because a feasible solution which is less than the objective function value of the given optimal

   x

   ij

   solution * exists, it contradicts the assumption that the

   flow along the arc i, j sent instead of sending flow along the path from node i to node j. Here, the meaning of sending

   more flow along arc i, j is equivalent to sending the

   flow along the path from node j to node i. Therefore in this case after comparing the per unit cost to send one unit of flow along the path from node j to node i with the per unit

   optimum solution in given. Therefore, the transformed network G ' V , A' contains no negative cycles.

   cost to send one unit of flow along the arc i, j from node

   j to node i, a flow along the path associated with the cheaper

   cost of the two cases is created. In this case, l

   is the sum

   LEMMA 2.2. If the directed path node j in G ' V , A', the u .

   P i, j

   from node i to

   of the length of the directed path

   P j,i

   from node j to

   node i and

   cij

   in G ' V , A'. If there are multiple

   of path

   P r, s, the length of the tree path

   P r, s is

   directed paths P j,i from node j to node i, l is calculated by summing the minimum length of the directed

   wr ws .

   Generally, given the optimal basis associated with

   spanning tree O , because the length of the shortest path

   path and

   cij

   G ' V , A'. Here, let

   Ph i, j

   be the

   from node i to node j is equivalent to the length of the tree

   length of the both directed path among the multiple directed paths. Then the length l, the shortest path from node j to node i is l minPh j,i. Therefore, if the shortest

   path from node j to node i exists in G ' V , A' we obtain l l cij . But if the shortest path does not exist in

   path P i, j from node i to node j, we can compute the sensitivity analysis more easily by calculating the length of the tree path using the node potentials. This case is called CS2

   By this result, CS2 and CS1 are the same in spanning tree solution [2]. Given an optimal solution that the number

   of arcs with a flow of l x u is greater than n 1,

   G ' V , A', u by lemma 2.2.

   In case the number of arcs, with a flow of the

   ij ij ij

   there arcs with the intermediate flow always form cycle. Let C be a cycle that consist of arcs with intermediate flow, lij xij uij . Then the results of the sensitivity analysis

   with respect to an arc i, j that belong to cycle C is given

   lij xij uij , is greater than or equal to n 1, we can

   easily compute the upper bound or the lower bound. Given a spanning tree optimal solution where the number of arcs

   with a flow of lij xij uij is exactly equal to n 1, we

   in theorem 2.3.

   THEOREM 2.3. Given a non-tree optimal solution where the number of arcs with aflow of l x u is greater than

   can obtain the node potentials w associated with the spanning tree optimal solution because arcs with a flow of

   ij ij ij

   n 1, the range of CS2 with respect to an arc i, j

   lij xij uij

   consist of the optimum basis of the network

   that belongs to a cycle C is zero.

   G V , A. By using node potentials w we can compute

   the length of the shortest path more easily because the node potentials w is the length of the tree path with respect to the

   PROOF. Given a non-tree optimal solution arcs with intermediate flow always form cycles. Let C be a cycle that consists of arcs with the intermediate flow. Then

   optimum basis O . We call this case as CS1.

   i, j c

   cij 0 if the cost of cij

   of an arc i, j

   is changed

   THEOREM 2.2. If O is an optimal basis and w is the node potentials with respect to O , then the length of the tree path P r, s from node r to node s is wr ws .

   to cij cij , then the value of the cycle C is

   (11)

   PROOF. We compute

   P r, s

   using the fact that

   If 0 (or 0 ) then it is better to send the flow in the

   opposite direction (or same direction) of cycle to improve

   cij cij wi wj 0 , for every arc i, j O

   the objective function value. In this case, since the flow along cycle C is created, the given optimal solution

   structure P,Q, R

   may change. Therefore in order to

   maintain the given optimal solution structure P,Q, R, the range of has to be zero.

   because all w corresponding to the nodes in the path, other than the terminal nodes r and s, cancel each ofher in the expression wi wj is associated with the length

   i, j Pr ,s

3. CONCLUSIONS

   In this paper, we have categorized the sensitivity analysis of the minimum cost flow problem into two types. We define CS1 to be the acquirement of a region where the given optimum basis is unchanged. This is the well known method applicable to a tree solution. However CS1 can not be applied to a non-tree solution or a degenerate tree solution. So we proposed the CS2 that finds the region where the upper bound valued arcs in the optimum solution maintain upper bound valued, low bound valued arcs maintain lower bound valued, and intermediate valued arcs maintain intermediate valued. This CS2 provides the

   generalized concept of the sensitivity analysis for the optimum solution of the minimum cost flow problem.

4. REFERENCES

1. D. J. Pannell, Sensitivity Analysis of Normative Economic Models: Theoritical Framework And Practical Strategies Agricultural Economics, 1997, 16: 139-152.

2. G. L. Nemhauser and Kan, Hand Books in Operations Research and Management Sci. 1 (North Holland) 321 323, 1989.

3. Hoyeon Chung, A Study on the Sensitivity Analysis for a Non-tree Solution and the Performance Improvement of the minimum Cost Flow Inabl, Dissertation of the Seul Nation University, 1994.

4. J. D. Jordan, The Average Network Flow Problem Shortest Path and Minimum Cost Formulation, Algorithms, Heuristics and Complexity, Ph. D. Thesis, Air Force Institute of Technology, 2012.

5. K. G. Marty, Network Programming (Prentice – Hall Inc), 1992.

6. N. G. Hall, M. E. Posner, Sensitivity Analysis for Scheduling Problems, Journal of Scheduling, 2004, 7:49:83.

7. N. Ravi and R. E. Wendell, The Tolerance Approach to Sensitivity Analysis in Network Linear Programming Networks, 1988, 18 159 -171.

8. Ravindra K. Ahuji, T. L. Magranti, and J. B. Orlin. Network Flows (Prentice-Hall Inc), 1993.

9. R. Ramaswamy, J. B. Orlin, N. Chakravarti, Sensitivity Analysis for Shortest Path Problems and Maximum Capacity Path Problems in Undirected Graph. Math. Program, 2005, Ser A 102: 355-364.

10. Tomas Gal, Postoptimal Analysis, Parametric Programing and Related Topic (McGraw Hill), 1979.

11. W. H. Cunningham, Theoritical Properties of the Network Simplex Method, Math of open Res, 1979, 4 (2) 196 200.

12. H. Chung, S. Park, Sensitivity Analysis Maintaining the Structure of the Optimum Solution in Minimum Cost Flow Problems. Proceedings of APDSI Conf., 1996: 1149-1156.