"近年来最小费用流问题的算法研究综述"

In recent decades, combinatorial optimization has experienced rapid development, with network flow being one of the extensively researched problems in the field. The minimum cost flow, as the most basic network flow model, plays a crucial role in the socioeconomic development and has garnered rich research achievements. This paper primarily focuses on several minimum cost flow problems arising from production practice in recent years. Firstly, it introduces the domestic and international research dynamics regarding the minimum cost flow problem. Subsequently, it presents the algorithmic concepts, steps, and complexities of four classical algorithms for solving the minimum cost flow problem: the negative cycle algorithm, the shortest path algorithm, the primal-dual algorithm, and the network simplex algorithm. Furthermore, aiming at the minimum cost flow problem with vertex flow demands (MICF), this study proposes an improved model based on the existing production network model (MNF) and enhances the existing algorithms for MICF. Experimental results demonstrate that the performance of the improved algorithm has been enhanced, effectively overcoming the issue of the original algorithm's application in large complex networks, which often leads to massive network structures. Keywords: combinatorial optimization, network flow, minimum cost flow, flow, production network model, MICF, algorithm.