Min Cost Flow: Cycle Cancelling Algorithm and ILP Formulation
Channel: Ben Rosenberg
Date: 2023-01-09

In this video, I go over the Min Cost Flow problem, and two different ways of solving it, one algorithmic and one computational. 

Max Flow video: https://www.youtube.com/watch?v=GOwt6cISaG4
GurobiPy implementation (GitHub gist): https://gist.github.com/benrosenberg/1670ddd0e57ed01ecaa1ec00dca66a48 

00:00 - Introduction and prerequisites
00:42 - What is the Min Cost Flow problem?
01:30 - Comparison between MCF and Max Flow
02:19 - Mathematical formulation of MCF
04:50 - MCF may not be solvable
06:49 - Rewriting MCF as Max Flow
12:25 - Solving MCF: Cycle Cancelling Algorithm
18:47 - MCF as an Integer Linear Program
21:05 - GurobiPy implementation of MCF
24:12 - Conclusion and attributions