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

Tran Quoc Chien^{1} and Ho Van Hung^{2}

^{1}The University of Education, University of Danang, Danang, Vietnam

^{2}Quangnam 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 *E _{v}* is the set of edges incident vertice

The symbol *r* is the commodity number, *q _{i}*> 0 is the coefficient of conversion of goods

Given the following functions:

*Edge passing capacity function ce:E*®*R ^{*}, *where

*Edge service coefficient function ze:E*®*R ^{*}, where ze*(

*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*, *be _{i}*:

*Node switch cost function i, i=*1*..r, bv _{i}*:

The sets ((*V*, *E*, *ce, ze*,* cv*, *zv*,{*be _{i},bv_{i}*,

à *Note*: If *be _{i}*(

Let *p* be the path from node *u* to node *v* through edges *e _{j}*,

*p* = [*u, e*_{1},* u*_{1},* e*_{2},* u*_{2},* …, e _{h}, u_{h}, e_{h+}*

The cost of circulating a converted unit of commodity of type *i*, *i* = 1..*r*, passing the path *p*, is denoted by the symbol *b _{i}*(

**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*, {*be _{i}, bv_{i}*,

Denote *P _{i,j }* is the set of paths from node

For each path *p**P _{i,j}*,

Denote *P _{i,e}* the set of paths in

Denote* P _{i,v}* the set of paths in Pi passing through the node

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*, {*be _{i}, bv_{i}*,

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 *dist _{i,j}*(

Set *a*(*le,lv*,*j*) = min{*dist _{i,j}*(

Consider the problem (*D** _{a}*):

**Lemma 4.1.**The problem (*D*) is equivalent to the problem (*D*) 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._{a}

*Proof** *

Denote *min*(*D*) and *min*(*D** _{a}*), respectively, the optimal values of the problem (

From (12) and (13), it follows min(*D*) = *min*(*D** _{a}*).

Next, if (*le,lv,**j*) is an optimal solution of the problem (*D** _{a}*), then (

*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 (*D** _{a}*).

**5.Algorithm**

** ****Ideas**

The algorithm consists of a number of iterative steps, through the function *length _{i}*(

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=(

** Output** : Maximal flow

*F* = {*x _{i,j}*(

with total cost not over the limit cost *B*.

*Procedure*

Note *n*=|*V*|, *m*=|*E*|, *B _{f}* total cost of the flows

Calculate *bmin*, the smallest cost in the paths from the source *s _{i,j }*to the destination

*bmin* = min{*b _{i}*(

Calculate *bmax*, the largest cost of the paths from the source *s _{i,j }*to the destination

*bmax* = max{*b _{i}*(

Set

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

for *e**E *: *le*(*e*)=*d*; *x _{i,j}*(

*j* = *d***/***bmin *; *fv *= 0; *B _{f}* = 0 ; (18)

**do**

{

Use the algorithm to find the source-destination pair (*s _{i,j}, t_{i,j}*), 1£

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*.*b _{imin}*(

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

Flow adjustments:

“*e**p*, *x _{i,j}*(

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

*j* = *j*.(1+*e*.*B*’**/***B*) ; *B _{f}* =

} **while** (*a* < 1)

Modifying the resulting flows *F* and flow value *fv.*

*x _{i,j}*(

*fv* = *fv /* ;

Modifying flows on scalar edge

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

for (*j*=1 ; *j*<=*k _{i}* ;

for scalar *e*Î*E*

if *x _{i,j}*(

{*x _{i,j}*(

else

{*x _{i,j}*(

**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, …

*le*_{0}, *lv*_{0} and *j*_{0} are, respectively, initial values of the functions *le*, *lv* and *j*.

*le _{i}*,

*p _{i}* is the shortest path

*a*(*i*)= *a*(*le _{i}*,

*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 *c _{j}* the value of

**Note**. From the converting flows {*x*(_{i,j}*e*) |*e**E*,*i*=1..*r*,*j*=1..*k*} we can deduce the actual flows by dividing the converted flows_{i}*x*(_{i,j}*e*) by the conversion factor*q*,”_{i}*i*=1..*r*,*j*=1..*k*, “_{i}*e**E*.**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 *j*_{0} = *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(*w*^{–}^{2}*.k.n*^{3}*.*(*m*+*n*).ln(*m*+*n*+*bmax/bmin*)),

where *k*=*k*_{1}+…+*k _{r}*,

*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 *p _{i}*. We increase the

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(*n*^{3}) [7, 8], which inferred the shortest path finding algorithm between *k* pairs of destination source ends with complexity O(*k.n*^{3}). Inferring the complexity of the algorithm is

** **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(*n ^{n}*). 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(

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

%d bloggers like this: