Introduction to Minimum Cost Flow and the Network Simplex Algorithm

The minimum cost network flow (MCNF) problem is an important form of linear program that can be used to model a wide variety of network design and management decision problems. Given a flow network through which material must be routed, the goal in the MCNF problem is to determine the amount of material to transport through each arc of the network in order to satisfy all given supply and demand requirements, while minimizing the cost over the arcs used.

This problem is formulated as a linear program whose decision variables represent the flow values of each arc, with the objective of minimizing the sum of all flow costs, and with constraints to enforce flow conservation and arc capacity. Its special combinatorial basis structure allows for it to be solved much more efficiently than a general linear program through the use of a specialized algorithm called network simplex.

This talk will serve as an introduction to the MCNF problem and network simplex, discussing some major applications of the MCNF problem, and showing how and why the network simplex algorithm works. Familiarity with network flows and linear programming will NOT be assumed.

Event Topic

Discrete Applied Math Seminar