Minimum-Cost Single-Commodity Flow

S. Thomas McCormick

ABSTRACT

This article defines minimum-cost single-commodity flow, or just min cost flow (MCF) for short, and surveys what is known about algorithms for solving it. It shows that many network optimization problems can be modeled using MCF. Concepts of duality and complementary slackness that are crucial for constructing algorithms and recognizing optimality are covered. We show how to compute feasible primal and dual solutions, and fundamental operations for finding an improvement to a primal or dual solution. Classic algorithms, such as primal-dual and out-of-kilter, and the use of scaling to make these run in polynomial time, are briefly covered. We cover the practically important successive approximation algorithm in more detail, including the technique used to make it strongly polynomial. Finally, the most widely used MCF algorithm in practice, network simplex, is covered in some detail.