# International Journal of Computer Networks & Communications (IJCNC)

AIRCC PUBLISHING CORPORATION

# ijcnc 6

Extended Linear Multi-Commodity Multi-Cost Network And Maximal Flow Limited Cost Problems

Tran Quoc Chien1 and Ho Van Hung2

1The University of Education, University of Danang, Danang, Vietnam

2Quangnam University, Tamky, Vietnam

Abstract

The Graph is a powerful mathematical tool applied in many fields as transportation, communication, informatics, economy, … In an ordinary graph, the weights of edges and vertexes are considered independently where the length of a path is the sum of weights of the edges and the vertexes on this path. However, in many practical problems, weights at a vertex are not the same for all paths passing this vertex but depend on coming and leaving edges. The presented paper develops a model of the extended linear multi-commodity multi-cost network that can be more exactly and effectively applied to model many practical problems. Then, maximal limit cost flow problems are modeled as implicit linear programming problems. On the base of dual theory in linear programming, an effective approximate algorithm is developed.

Keywords

Graph, Network, Multi-commodity Multi-cost Flow, Optimization, Linear-Programming.

1.Introduction

Network and its flow is a powerful mathematical tool applied in many fields as transportation, communications, informatics, economics, and so on. So far, most of the applications in the new graph solely considers to the weight of edges and nodes independently, in which the path length merely is the sum of weights of edges and nodes along the path. However, in many practical problems, the weight at one node is not the same for all paths passing through that node, but also depends on coming and leaving edges. For example, the transit time on the transport network depends on the direction of transportation: turn right, turn left or go straight, even some directions are forbidden. Paper [2] proposes switching cost only for directed graphs. Therefore, it is necessary to build an extended mixed network model in order to apply more accurate and effective modeling of practical problems. Multi-commodity flow in traditional network problems have been studied in the papers [1,3,4,5,6]. Multi-commodity flow in extended network problems with extended transport networks were studied in the papers [7-11]. The paper[12] studies maximal multi-commodity multi-cost flow problems.

The paper builds the extended multi-cost multi-commodity model in sections 2 and 3 to enable modeling of more accurate and efficient real problems. Next, in section 4, the maximal limit cost multi-commodity multi-cost flow problem is defined by a hidden linear programming problem model. Based on the duality theory of linear programming, an approximation algorithm with polynomial complexity is developed in section 5.

2.Extended Linear Multi-Commodity Multi-Cost Network

Given mixed graph G = (V, E) with node set V and edge set E. The edges may be undirected or directed. The symbol Ev is the set of edges incident vertice vÎV. There are many kinds of goods circulating on the network. Commodities share the capacities of the edges, but have different costs. The undirected edges represent the two-way edge, in which the goods on the same edge, but reverse directions share the capacity of the edge.

The symbol r is the commodity number,  qi> 0 is the coefficient of conversion of goods i, i =1..r.

Given the following functions:

Edge passing capacity function ce:E®R*, where ce(e) is the passing capability of the edge eÎE.

Edge service coefficient function ze:E®R*, where ze(e) is the passing ratio of the edge eÎE (the real capacity of the edge e is ze(e).ce(e)).

Node passing capability function  cv:V®R*, where cv(u) is the passing capability of  the node uÎV .

Node service coefficient function zv:V®R*, where  zv(u) is the passing ratio of the node vÎV (the real capacity of the node v is zv(v).cv(v)).

The tuples (V, E , ce, ze, cv, zv) are called extended networks.

Edge cost function i, i=1..r, bei:E®R*, where bei(e) is the cost of passing e a converted unit of commodity of type i. Note that with 2-way paths, the cost of each way may vary.

Node switch cost function i, i=1..r, bvi:V´Ev´Ev®R*, where bvi(u,e,e’) is the cost of transferring a converted unit of commodity of type i from edge e through u to edge e’.

The sets ((V, E, ce, ze, cv, zv,{bei,bvi, qi|i=1..r}) are called the extended linear multi-commodity multi-cost network.

à Note: If bei(e)=¥, commodity of type i is prohibited from circulation on path e. If  bvi(u,e,e’) = ¥, comodity of type i is banned from path e through u to path e.

Let p be the path from node u to node v through edges ej, j=1..(h+1), and nodes  uj, j=1..h  as follows

p = [u, e1, u1, e2, u2, …, eh, uh, eh+1, v]

The cost of circulating a converted unit of commodity of type i, i = 1..r, passing the path p, is denoted by the symbol bi(p), and defined by the following formula:

3.Multi-Commodity Flow Problems In Extended Linear Multi-Commodity Multi-Cost Network

Given a multi-cost multi-commodity network G=(V,E,ce, ze, cv, zv, {bei, bvi, qi|i=1..r}). Assume, for each commodity of type i, i=1..r, there are ki source-target pairs (si,j, ti,j), j=1..ki, each pair assigned a quantity of commodity of type i, that is necessary to move from source node si,j to target node ti,j.

Denote  Pi,j  is the set of paths from node si,j to node ti, in G, which commodity of type i can be passed, i=1..r, j=1..ki. Set

For each path pPi,j, i=1..r, j=1..ki,  denote xi,j(p) the flow of converted commodity of type i from the source node si,j to the destination node ti,j  along the path  p, i=1..r, j=1..ki.

Denote Pi,e the set of paths in Pi passing through the edge e, “eÎE.

Denote Pi,v the set of paths in Pi passing through the node v, “vÎV.

is called a multi-commodity flow on the linear extended multi-commodity multi-cost  network, if it satisfies the following edge and node capacity constraints:

4. MAXIMAL LIMITED COST MULTI-COMMODITY FLOW PROBLEMS

Given an extended linear multi-commodity multi-cost network G=(V,E, ce, ze, cv, zv, {bei, bvi, qi|i=1..r}).  Assume, for each commodity of type i, i=1..r, there are ki source-target pairs (si,j, ti,j), j=1..ki, each pair assigned a quantity of commodity of type i, that is necessary to move from source node si,j to target node ti,j. Given a limit cost B.

The task of the problem is to find the multi-commodity flow such that the value of  the flow fv is maximal. At the same time, the total cost of the flow does not exceed B.

The problem is expressed by an implicit linear programming model (P) as follows:

The dual linear programming problem of (P), called (D), is constructed as follows: each edge eÎE is assigned an dual variable le(e), each node vÎV is assigned an dual variable lv(v) while the dual variable j  assigns the constraint of cost. The problem (D) states the following

Denote disti,j(le,lv,j)  the shortest path length from si,j  to ti,j calculated by function  lengthi(p), “i=1..r, “j=1..ki.

Set a(le,lv,j) = min{disti,j(le,lv,j) | i=1..r, j=1..ki}

Consider the problem (Da):

• Lemma 4.1. The problem (D) is equivalent to the problem (Da) such that their optimal value are equal and the optimal solution of one problem derives the optimal solution of the other problem and vice versa.

Proof

Denote min(D) and min(Da),  respectively, the optimal values of the problem (D) and the problem (Da) . Given functions le: E®R*lv:V®R*, j > 0. Set

From (12) and (13), it follows min(D) = min(Da).

Next, if (le,lv,j) is an optimal solution of the problem (Da), then (le,lv’,j’) where

le’(e) = le(e)/a(le,lv,j), “eÎE, lv’(v) = lv(v)/a(le,lv,j), “vÎV, j’ = j/a(le,lv,j).

is an optimal solution of problem (D).

Conversely, if (le,lv,j) is an optimal solution of the problem (D), then (le,lv,j) is an optimal solution of the problem (Da).

5.Algorithm

Ideas

The algorithm consists of a number of iterative steps, through the function lengthi(p), pPi, i=1..r. At each iteration step, find the shortest path p, with respect to the length function lengthi(p))  between the source-destination pairs and convert c units of exchange through p, where c is the minimal edge and node capacity on this path.

Then change the value of functions le, lv and j..The algorithm stops once a ³ 1. The initial value of le, lv and j depends on the approximate value to be achieved.

Algorithm

Input: Extended multi-cost multi-commodity network G=(V,E, ce, ze, cv, zv, {bei, bvi, qi|i=1..r}). Assume, for each commodity of type i, i=1..r, there are ki source-target pairs (si,j, ti,j), j=1..ki, each pair assigned a quantity of commodity of type i, that is necessary to move from source node si,j to target node ti,j. Given a limited cost B, an approximation ratio w.

Output : Maximal flow F represents a set of converged flows at the edges

F = {xi,j(e) | eE, i=1..r, j=1..ki}

with total cost not over the limit cost B.

Procedure

Note  n=|V|, m=|E|, Bf total cost of the flows F.

Calculate bmin, the smallest cost in the paths from the source si,j to the destination ti,j, i=1..r, j=1..ki :

bmin = min{bi(p) | i=1..r, j=1..ki, pÎPi,j}.                                                               (14)

Calculate bmax, the largest cost of the paths from the source si,j to the destination ti,j, i=1..r, j=1..ki.

bmax = max{bi(p) | i=1..r, j=1..ki, pÎPi,j}.                                                             (15)

Set

e = 1- ; d = (1+e);                                                                                                           (16)

for e: le(e)=d; xi,j(e)=0 ; for vÎV :  lv(v)=d ;                                                          (17)

j = d/bmin ; fv = 0; Bf = 0 ;                                                                                           (18)

do

{

Use the algorithm to find the source-destination pair (si,j, ti,j), 1£i£r and 1£j£ki, having the shortest path from si,j to ti,j calculated by the length function lengthi(.).Note that the path p must be valid

for goods of type i, i.e., not containing the edge with edge cost ¥ or the node with the switch cost¥.

Note

imin and  jmin the indexes of source-destination pairs with the shortest path;

a  is the shortest path length;

p is the shortest path;

c is the minimal edge and node capacity on the path p, i.e.

c=min{min{ce(e).ze(e)|eÎp},min{cv(v).zv(v)|vÎp}};

B’ = c.bimin(p);

if (B’>B){  c = c.B / B’; B’ = B;  }

ep, xi,j(e)=xi,j(e)+c;le(e)=le(e).(1+e.c/(ce(e).ze(e)));                                                      (19)

vÎp, lv(v)=lv(v).(1+e.c/(cv(v).zv(v)));                                                                              (20)

j = j.(1+e.B/B) ;  Bf = Bf + B’ ; fv = fv + ;                                                                         (21)

} while (a < 1)

Modifying the resulting flows F and flow value fv.

xi,j(e)=xi,j(e) / ; “i=1..r, j=1..ki,”eE;                                                                                      (22)

fv = fv / ; Bf = Bf/;                                                                                                                   (23)

Modifying flows on scalar edge

for (i=1 ; i<=r ;i++)

for (j=1 ; j<=ki ;j++)

for scalar eÎE

if xi,j(e) >= xi,j(e’)// e’ is the opposite of the direction e

{xi,j(e) = xi,j(e)-xi,j(e’) ;  xi,j(e’)=0};

else

{xi,j(e’) = xi,j(e’)-xi,j(e) ;  xi,j(e)=0};

Proof Of Algorithm

Denote

D(0) the initial value of function D

fv(0) = 0 is the initial value of the flow F.

fv(i) is the value of the flow F after the loop i, i=1, 2, …

le0, lv0 and j0 are, respectively, initial values of the functions le, lv and j.

lei, lvi and ji correspond respectively to le, lv and j in the loop i. i=1, 2, …

pi is the shortest path p in the loop i. i=1, 2, …

a(i)= a(lei,lvi,ji), i = 1, 2, …

c(i) is the value of c in the loop i. i = 1, 2, …

We have

Proof. Consider any edge e. We have :

For each transfer of ce(e)ze(e) converted units of commodities through e, the length le(e) of e increases by a factor ³ (1+e). Indeed, at each iteration we only transfer c£ce(e)ze(e) converted units of commodities through e. So, in order to transfer of ce(e)ze(e) converted units of commodities through e, commodities must be transferred through e at least in one iteration. Suppose it starts at iteration i. Let q be the number of iterations to transfer of ce(e)ze(e) converted units of commodities through e. Denote cj  the value of c at the j-th transfer through e, j=1..q. Denote l the last iteration that transfers cq converted units of commodities through e. We have

• Note. From the converting flows {xi,j(e) | eE, i=1..r, j=1..ki } we can deduce the actual flows by dividing the converted flows xi,j(e) by the conversion factor qi,”i=1..r, j=1..ki, “eE.
• Lemma 5.3. The total flow cost in t iterations does not exceed B.. That is, the total cost of the flow after divide by does not exceed B.

Proof.  We have j0 = d/bmin. After (t-1) iterations, we have a(t-1) <1, it mean

6.Algorithm Complexity

Theorem 6.1. The algorithm has a complexity of

O(w2.k.n3.(m+n).ln(m+n+bmax/bmin)),

where k=k1+…+kr, m is the number of edges in the graph, n is the number of vertices.

Proof. Consider the iterations i. Suppose e is the edge capacity of passing the smallest ce(e)ze(e)=c(i) along the shortest path pi. We increase the lei(e) of e factor (1+e). Considering any e, let te be the number of iterations in which e has minimal capacity on corresponding path. Since le0(e) =d  and let(e) <1+e, we have

Then, each edge eÎE corresponds to at most t* times of finding shortest paths.

Similarly, each node vÎV corresponds to at most t* times of finding shortest paths.

So the times of finding shortest paths £ (m+n).t*.

The algorithm that finds the shortest path between the two source-destination ends has a complexity of O(n3) [7, 8], which inferred the shortest path finding algorithm between k pairs of destination source ends with complexity O(k.n3). Inferring the complexity of the algorithm is

7. Conclusions

The paper develops a model of extended linear multi-commodity multi-cost network that can be more exactly and effectively applied to model many practical problems. Then, maximal limit cost flow problems are modeled as implicit linear programming problems. On the base of dual theory in linear programming an effective approximate algorithm is developed. Correctness and algorithm complexity are justified. The results of this paper are the basis for studying the multi-commodity multi-cost flow optimization problem.

At last we emphasis that there is no efficient method solving implicit linear problems. Otherwise, it is almost impossible to present this problem as an explicit linear problem, for the number of all paths p, which determines the variables x(p), is as big as O(nn).   So, in case this problem is converted to an explicit linear problem and solved by any known method (f.e. simplex method), the complexity is much bigger than O(nn), that is not practically acceptable.

References

[1]     Naveen Garg, Jochen Könemann: Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems, SIAM J. Comput, Canada, 37(2), 2007,  pp. 630-652.

[2]     Xiaolong Ma, Jie Zhou: An Extended Shortest Path Problem with Switch Cost Between Arcs,              Proceedings of the International MultiConference of Engineers and Computer Scientists 2008 Vol IIMECS 2008, 19-21 March, 2008, Hong Kong.

[3]     Tran Quoc Chien: Linear multi-channel traffic network,  Ministry of Science and Technology, code    B2010DN-03-52.

[4]     Tran Quoc Chien, Tran Thi My Dung: Application of the shortest path finding algorithm to find the maximum flow of goods. Journal of Science & Technology, University of Danang, 3 (44) 2011.

[5]     Tran Quoc Chien: Application of the shortest multi-path finding algorithm to find the maximum simultaneous flow of goods simultaneously. Journal of Science & Technology, University of Danang, 4 (53) 2012.

[6]     Tran Quoc Chien: Application of the shortest multi-path finding algorithm to find the maximal simultaneous flow of goods simultaneously the minimum cost. Journal of Science & Technology, Da Nang University, 5 (54) 2012.

[7]     Tran Quoc Chien: The algorithm finds the shortest path in the general graph, Journal of Science & Technology, University of Da Nang, 12 (61) / 2012, 16-21.

[8]     Tran Quoc Chien, Nguyen Mau Tue, Tran Ngoc Viet: The algorithm finds the shortest path on the extended graph. Proceeding of the 6th National Conference on Fundamental and Applied Information Technology (FAIR), Proceedings of the Sixth National Conference on Scientific Research and Application, Hue, 20-21 June 2013. Publisher of Natural Science and Technology. Hanoi 2013. p.522-527.

[9]     Tran Quoc Chien: Applying the algorithm to find the fastest way to find the maximum linear and simultaneous minimum cost on an extended transportation network, Journal of Science & Technology, University of Da Nang . 10 (71) 2013, 85-91.

[10]   Tran Ngoc Viet, Tran Quoc Chien, Nguyen Mau Tue: Optimized Linear Multiplexing Algorithm on Expanded Transport Networks, Journal of Science & Technology, University of Da Nang. 3 (76) 2014, 121-124.

[11]   Tran Ngoc Viet, Tran Quoc Chien, Nguyen Mau Tue: The problem of linear multi-channel traffic flow in traffic network. Proceedings of the 7th National Conference on Fundamental and Applied Information Technology Research (FAIR’7), ISBN: 978-604-913-300-8, Proceedings of the 7th National Science Conference “Fundamental and Applied Research IT “, Thai Nguyen, 19-20 / 6/2014. Publisher of Natural Science and Technology. Hanoi 2014. p.31-39.

[12]   Tran Quoc Chien, Ho Van Hung: Extended linear multi-commodity multi-cost network and maximal flow finding problem. FAIR-2017.

Authors

Ass. Prof. DrSc. Tran Quoc Chien (http://scv.ued.udn.vn/ly_lich/chi_tiet/275).He  has 14 papers in SCIE of Journal (http://www.kybernetika.cz/contact.html). Born in 1953 in Dien Ban, Quang Nam, Vietnam. He graduated from Maths_IT faculty. He got Ph.D Degree of maths in 1985 in Charles university of Prague, Czech Republic and hold Doctor of Science in Charles university of Prague, Czech Republic in 1991. He received the tittle of Ass. Pro in 1992. He work for university of Danang, Vietnam. His main major: Maths and computing, applicable mathematics in transport, maximum flow, parallel and distributed process, discrete mathemetics, graph theory, grid Computing, distributed programming.

M.Si. Ho Van Hung (http://qnamuni.edu.vn/viewLLKH.asp?MaGV=134). Born in 1977 in Thang Binh, Quang Nam, Vietnam. He graduated from Faculty of Information Technology – College of Sciences – Hue University in 2000. He got master of science (IT) at Danang university of technology. His main major: Applicable mathematics in transport, maximum flow, parallel and distributed process, graph theory and distributed programming.