 Open Access
 Total Downloads : 271
 Authors : Mahdalena, Herman Mawengkang
 Paper ID : IJERTV3IS051506
 Volume & Issue : Volume 03, Issue 05 (May 2014)
 Published (First Online): 28052014
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
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.

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

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 nontree 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 nontree 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


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 nontree 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.

REFERENCES

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

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

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

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.

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

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

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

Ravindra K. Ahuji, T. L. Magranti, and J. B. Orlin. Network Flows (PrenticeHall Inc), 1993.

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: 355364.

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

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

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