tailieunhanh - Minimum cost network flows: Problems, algorithms, and software

We present a wide range of problems concerning minimum cost network flows, and give an overview of the classic linear single commodity Minimum Cost Network Flow Problem (MCNFP) and some other closely related problems, either tractable or intractable. We also discuss state-of-the-art algorithmic approaches and recent advances in the solution methods for the MCNFP. Finally, optimization software packages for the MCNFP are presented. | Yugoslav Journal of Operations Research 23 (2013), Number 1, 3-17 DOI: MINIMUM COST NETWORK FLOWS: PROBLEMS, ALGORITHMS, AND SOFTWARE Angelo SIFALERAS Department of Technology Management, University of Macedonia, Economic and Social Sciences, Loggou-Tourpali, Naoussa 59200, Greece sifalera@ Invited review Received: November 2012 / Accepted: January 2013 Abstract: We present a wide range of problems concerning minimum cost network flows, and give an overview of the classic linear single-commodity Minimum Cost Network Flow Problem (MCNFP) and some other closely related problems, either tractable or intractable. We also discuss state-of-the-art algorithmic approaches and recent advances in the solution methods for the MCNFP. Finally, optimization software packages for the MCNFP are presented. Keywords: Mathematical Programming, Combinatorial Optimization, Optimization Software. MSC: 65K05, 90C27, 90B10. 1. INTRODUCTION Network Optimization [2], [25], [66], [72], [87] makes a large part of Combinatorial Optimization [57], [73], and present a model often used for a large number of real-world applications [63] in communications, informatics, transportation, construction projects [96], water resources management [50] and supply chain management [11], [12]. A wide category of Network Optimization problems constitute the MCNFP, and several other well-known optimization problems are special cases of MCNFP. 4 A. Sifaleras / MCNFP: Problems, Algorithms, and Software Let G = (N, A) be a directed network with n nodes and m arcs, where N and A are the sets of nodes and arcs, respectively. Each arc (i,j) ∈ A has a cost cij that denotes the unit shipping cost along the arc (i,j). Each arc (i,j) is also associated with an amount xij of flow on the arc, a lower bound lij and an upper bound uij of the flow; thus lij ≤ xij ≤ uij. However, if uij = + ∞, then the MCNFP is called uncapacitated (also known as transshipment problem). We associate a number