Technical Report Number
The minimum concave cost network ﬂow problem (MCCNFP) has many applications in areas such as telecommunication network design, facility location, production and inventory planning, and trafﬁc scheduling and control. However, it is a well known NP-hard problem, and all existing search based exact algorithms are not practical for networks with even moderate numbers of vertices. Therefore, the research community also focuses on approximation algorithms to tackle the problems in practice. In this paper, we present an improved local search algorithm for the minimum concave cost network ﬂow problem based on multi-cycle reduction. The original cycle reduction local search algorithm as proposed by Gallo and Sodini considers only negative cost single cycles; however, we ﬁnd that such cycle reduction is not complete. We show that negative cost multi-cycles may exist in a network with concave edge costs that has no negative cost cycles, and an existing ﬂow can be reduced to an adjacent neighboring ﬂow with lower cost by redirecting ﬂows along these negative multi-cycles. In this paper, we present an improved local search algorithm based on multi-cycle reduction. We evaluate our proposed algorithm in networks with a simple concave edge cost in different topologies and sizes. The experimental results show that the original cycle reduction algorithms can improve the quality of solutions obtained from a simple minimum cost augmentation approximation heuristic (LDF), and that a multi-cycle reduction yields more improvements; however, it reaches a point of diminished returns when we attempt to reduce more than bicycles.
Qiu, Ruibiao and Turner, Jon, "Improved Local Search Algorithms with Multi-Cycle Reduction for Minimum Concave Cost Network Flow Problems" Report Number: WUCSE-2004-74 (2004). All Computer Science and Engineering Research.