# An Efficient Algorithm for Solving Minimum Cost Flow Problem with Complementarity Slack Conditions

Authors: Yongwen Hu; Xiao Zhao; Jing Liu; Binyuan Liang; Chao Ma
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

This paper presents an algorithm for solving a minimum cost flow (MCF) problem with a dual approach. The algorithm holds the complementary slackness at each iteration and finds an augmenting path by updating node potential iteratively. Then, flow can be augmented at the original network. In contrast to other popular algorithms, the presented algorithm does not find a residual network, nor find a shortest path. Furthermore, our algorithm holds information of node potential at each iteration, and we update node potential within finite iterations for expanding the admissible network. The validity of our algorithm is given. Numerical experiments show that our algorithm is an efficient algorithm for the MCF problem, especially for the network with a small interval of cost of per unit flow.


---

## Body

## 1. Introduction

The minimum cost flow (MCF) problem is to find a minimal cost of a given amount flow from a set of supply nodes to a set of demand nodes in a directed network where each arc is assigned a cost and a capacity constraint. MCF problem plays a fundamental role in network optimization. On the one hand, many network flow problems, such as shortest path problem, maximal flow problem, and transportation problem, can be viewed as special cases of the MCF problem. On the other hand, the MCF problem has a remarkable wide range of applications [1] in the real word, for example, scheduling [2], agriculture [3], communications [4], health care [5, 6], and transportation [7].Since the MCF problem is a linear program, we can also find the optimal solution with linear programming methodologies. Indeed, many of various optimality conditions about the MCF problem and linear programming are derived by researchers. Thus, we can develop efficient algorithms for the MCF problem with theory of duality.Several algorithms have been designed for solving the MCF problem over past decades both from theoretical and from practical aspects. Many algorithms combing ingredients of both shortest path and maximal flow are developed to solve the MCF problem. These algorithms find an optimal solution by solving a sequence of the shortest path problem within maximum flow-like residual networks and augmenting path, such as the cycle-canceling algorithm [8], successive shortest path algorithm [9], and primal-dual and out-of-kilter algorithms [10]. They are equivalent in the sense that these algorithms perform the same sequence of strategy, and the key step is defining the residual network iteratively. Moreover, both cost and capacity are to be considered for defining the residual network, and some more arcs are to be introduced with negative cost, which make the original problem much more difficult to solve. Although none of the algorithms mentioned above has been shown to be a well complexity, they usually behave much better in practice compared to their theoretical analysis. Edmonds and Karp [11] proposed the first polynomial algorithm. Currently, an efficient polynomial time algorithm for the MCF problem was proposed by Orlin [12] and Vygen [13]. Some theoretical results and algorithms are given in [14–18] for solving the MCF problem or its variants. Recently, Vieira et al. [19] evaluated the practical performance of 4 algorithms on real networks. And Vernet et al. [20] used a success shortest path algorithm for dynamic graph. A recent survey on the MCF problem is given in [21].Our purpose in this paper is to present a new algorithm for solving the MCF problem. We consider the dual problem of MCF problem and derive the optimality conditions. The algorithm can find an augmenting path directly in a directed network when some dual variables (nodes potentials) of the MCF problem are updated iteratively in finite steps. In contrast to other algorithms, we do not need to define any residual network.This paper is organized as follows: Section2 derives optimality conditions of MCF problem with duality theory. Section 3 gives an iterative algorithm for the MCF problem. Section 4 discusses validity of the presented algorithm. Numerical experiment results and analysis of computational experiments are reported in Section 5. Section 6 contains some concluding remarks on the proposed algorithm for solving the MCF problem.


## 2. Optimality Conditions

LetG=N,A,C,U be a directed network with a node set N, an arc set A, a cost set C, and a capacity set U. Furthermore, a cost cij∈C and a nonnegative capacity uij∈U associated with each arc i,j∈A,∀i,j∈N. And we associate with each node i∈N a number bi which indicates its supply or demand depending on whether bi<0 or bi>0. Let node s and node t be the source node and sink node, respectively. And we assume that ∑i∈N,i≠s,tbi=0. The MCF problem can be stated as follows:(1)MCFminzx=∑i,j∈Acijxij∑j:i,j∈Axij−∑j:j,i∈Axji=v∗,i=s,∑j:i,j∈Axij−∑j:j,i∈Axji=−v∗,i=t,∑j:i,j∈Axij−∑j:j,i∈Axji=0,∀i∈N,i≠s,t,0≤xij≤uij,∀i,j∈A.The dual problem of MCF is(2)DMCFmaxω=v∗ps−v∗pt+∑i,j∈Auijpijpi−pj+pij≤cij,∀i,j∈A,piis free,∀i∈N,pij≤0,∀i,j∈A,i∈N,where pi and pij are the dual variables of the MCF problem. And we refer to pi and pij as the potential of node i and arc i,j,∀i∈N,∀i,j∈A, respectively.Letx=xij and p=pi,pij be a feasible solution of MCF and DMCF, respectively. If feasible solution x=xij and p=pi,pij are optimal solutions, according to theorem of commentary slackness, the following conditions will be satisfied:(3)xij=0,ifpi−pj+pij<cij,∀i∈N,i,j∈A,(4)xij=uij,ifpij<0,∀i,j∈A.Sincepi is free ∀i∈N, let pij=min0,cij+pj−pi, then we have pij≤0. Therefore, we can find a feasible solution p=pi,pij of DMCF where the value of pij is defined above ∀i∈N,∀i,j∈A. Thus, the complementary slackness conditions (3) and (4) are equal to the following conditions:(5)xij=0,ifpi−pj<cij,∀i∈N,i,j∈A,(6)xij=uij,ifpi−pj>cij,∀i∈N,i,j∈A.Therefore, if feasible solutionx=xij is an optimal solution of MCF, then x will satisfy conditions (5) and (6). On the contrary, for the arc i,j∈A satisfying pi−pj=cij, we have 0≤xij≤uij. In other words, we can find an augmenting path where each arc i,j∈A on the path such that pi−pj=cij when the value of flow is not the maximum flow in a network. We refer to arc i,j∈A satisfying pi−pj=cij as the admissible arc, and let G′=N′,A′,C′,U′ be an admissible network satisfying that N′⊆N,A′⊆A,C′⊆C,U′⊆U,pi−pj=cij,∀i,j∈A′.


## 3. An Iterative Algorithm for Solving MCF

It is clear thatxij=0,∀i,j∈A is an optimal solution with a flow valued 0. In order to get an optimal solution of MCF with a given amount of flow, we iteratively augment flow holding the complementary slackness condition (5) and (6) at each iteration. And flow can be augmented after we find an augmenting path within the admissible network. Moreover, a new admissible network can be given by updating the potential of node when we cannot find an augmenting path and flow is not the maximal flow. Let V be a number of given amount of flow. We now describe formally our algorithm for solving the MCF problem (Algorithm 1).Algorithm 1
Initialization: initialize node potential pi=0,∀i∈N. Let xij=0,i,j∈A, be an initial optimal solution with a flow valued 0. Label source node 0,+∞. Set S=s,S¯=N−S.
While ∑i:s,i∈Axsi≥V or θ cannot be found
While t∉S
For i∈S
θi=minminj:i,j∈S,S¯∩Api−pj<cijcij−pi+pj,minj:j,i∈S¯,S∩Apj−pi>cijpj−pi−cij
End
θ=mini∈Sθi
pi=pi+θ,i∈S,pi,i∈S¯.
If pi−pj=cij then
i,j∈R
End
If t∈S then
For ∀i∈S,j∈S¯
If i,j∈R and xij<uij
Label nodej with a label i,δj, where δj=minδi,uij−xij, S=S∪j.
End
If j,i∈R and xji>0 then
Label nodej with a label −i,δj, where δj=minδi,xji,S=S∪j.
End
End
xij=xij+δt,xij∈μ+,xij−δt,xij∈μ−,xij.
End
End
EndNext, we will give the validity of the proposed algorithm.


## 4. Validity of the Proposed Algorithm

The validity of the above algorithm depends mainly from the following results:Lemma 1.
When the current flow is not the maximal flow in a network, at least one admissible arc can be found after updating node potential.Proof.
It is clear that there is at least one augmenting path if current flow is not the maximal flow in a directed network. Therefore, we havexij<uij for some forward arc i,j or xji>0 for some backward arc j,i,∀i∈S,j∈S¯. Otherwise, node j will be labeled and j∈S according to the presented algorithm. Then, we can find θ and update node potential by Algorithm 1. Thus, at least one new admissible forward arc i,j,pi−pj=cij or backward arc j,i,pj−pi=cji will be found.Theorem 1.
The proposed algorithm finds an augmenting path in a finite iteration when the current flow is not the maximal flow.Proof.
Letn be the number of nodes in a network G=N,A,C,U, and there are at most n−1 arcs on a path μ from the source node to sink node. According to Lemma 1, the presented algorithm can find an augmenting path in n−1 iterations, which implies Theorem 1.Theorem 2.
After augmenting a flow of valuev by our algorithm, then the new feasible flow valued v′=v+δt is the minimum cost flow valued v′.Proof:.
the algorithm begins a feasible flowxij=0,∀i,j∈A, and feasible flow xij=0,∀i,j∈A is the minimum cost flow valued 0. Furthermore,the proposed algorithm holds the complementary slackness condition (5) and (6) at each iteration. Therefore, augmented flow updated by Algorithm 1 is the optimal solution of a minimum cost flow valued v′, which gives Theorem 2.


## 5. Numerical Experiment

In this section, the computational experimental results are presented in order to verify the performance of the presented algorithm. The presented algorithm has been coded with Matlab and run on PC with Intel® Core™ i5-7300HQ CPU (2.5 GHz) and RAM 8 GB. The tested problem is generated by the well-known Waxman network topology generator with the method proposed by Waxman [22]. All nodes of the generated problem are a Poisson process in the plane with scaled. Nodes i and j are connected with probability pi,j=αe−di,j/βL, where α is the maximal link probability, β is a parameter to control length of the arcs, di,j is the Euclidean distance between node i and j, and L is the maximal distance between any two nodes. For the network generated by the Waxman generator, we randomly give a cij and uij for each arc i,j∈A. The computational experiments are performed on a network with different scales (n varied from 10 to 200). Let nm be the number of nodes (arcs) of the generated network. And for a fixed n and m, a set of 10 instances are solved by our proposed algorithm and the successive shortest path algorithm (SSPA) [9] in order to make computational comparison. Furthermore, for a fixed n, our algorithm and SSPA are performed on a network with different number of arcs and cij,i,j=1,2,…,n. For the sake of simplicity, the algorithm proposed in [9] is named as Algorithm A1 and the algorithm proposed in this paper as A2. The numerical experiment results are reported in Table 1. The column titled “AVER.” in Table 1 provides an average CPU time out of 10 runs in the execution.Table 1
CPU time on network withn varying from 10 to 200 and two different intervals of cij.
No. of nodes
No. of arcs (average)
AVER. CPU time (s),c∈1,10
AVER. CPU time (s),c∈1,1000
A1
A2
A1
A2
10
32
7.964
0.050
8.002
0.054
10
43
8.245
0.059
8.306
0.064
15
62
8.430
0.060
8.517
0.078
15
99
8.642
0.079
8.726
0.085
20
86
8.578
0.069
8.469
0.086
20
184
8.860
0.102
8.872
0.131
30
210
8.954
0.087
8.936
0.164
30
418
9.014
0.166
9.201
0.258
40
371
8.976
0.092
9.005
0.255
40
763
9.356
0.278
9.428
0.423
50
572
9.169
0.127
9.225
0.397
50
1186
9.628
0.364
9.617
0.673
80
1578
9.725
0.247
9.829
1.056
80
3083
10.427
0.853
10.526
2.502
100
2616
10.320
0.344
10.431
1.734
100
4857
10.569
1.550
10.726
6.438
200
9488
18.351
2.069
19.251
37.181
200
19482
210.358
23.429
221.852
143.759The numerical experiments indicate the following observations.A2 outperforms A1 in terms of CPU time in all cases. A2 runs approximately 9–140 times faster than A1 as “n” varies from 10 to 200 with cij∈1,10,∀i,j∈A. For a larger interval of cij∈1,1000,∀i,j∈A, A2 takes more CPU time compared with a smaller interval of cij∈1,10,∀i,j∈A. As the proposed algorithm described, the proposed algorithm holds information of node potential at each iteration, and we update node potential for expanding the admissible network. Therefore, we may find several admissible arcs after updating the node potential in an iteration for a smaller interval of cij, which implies that we find augmenting path(s) more efficiently compared with a larger interval of cij,∀i,j∈A.Furthermore, the numerical experiments show that the increased CPU time of A2 is greater than A1 when the number of nodes increased. And the largest number of nodes in the network generated by the Waxman generator on our PC is 200. Therefore, for a larger number of nodes (great than 200) and a great interval ofcij∈1,1000,∀i,j∈A in a network, A2 will take more CPU time compared to A1 for solving the MCF problem.


## 6. Conclusion

In this paper, we proposed an algorithm for solving the MCF problem with a dual approach which holds a complementary slackness conditions at each iteration. The key step of our algorithm is updating node potential, and flow can be augmented after updating node potentials in finite steps. Unlike existing algorithms such as successive shortest path algorithm and primal-dual algorithm, our algorithm does not find the residual network, nor find the shortest path iteratively. We conduct a numerical experiment to investigate the performance of the proposed algorithm. The results of the numerical experiment show that our algorithm reduces CPU time greatly compared with SSPA.In this paper, the cost of flow is fixed, and we plan to develop an algorithm for solving the MCF problem with fuzzy cost and constraints. In practice, it is worthwhile to study the case that we have a close-to-optimal solution for the MCF problem. It is fundamentally important to transform the multiobject assignment problem and multiobject transportation problem into the MCF problem, which could be our further study.



---

*Source: 2439265-2020-02-12.xml*