Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Lecture
Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
This lecture introduces the maximum flow problem, motivated by the Cold War era, where the US Army studied the railway network from Moscow to Berlin. The goal is to determine the maximum number of trains that can be transported between these cities. The lecture explains how to calculate the maximum flow through a network by analyzing the capacities of the arcs. It then transitions to the transhipment problem, aiming to minimize the total transportation cost by optimizing the flow reaching the destination. The concept of circulation is introduced, and the lecture details the formulation of the transhipment problem, including the addition of an artificial arc to track the flow. Constraints on flow conservation and arc capacities are discussed, leading to the problem's mathematical representation.