Decomposition Methods for the Unsplittable Flow Problem

Explore decomposition methods for solving the Unsplittable Flow Problem in this 53-minute seminar by François Lamothe from Université du Québec à Montréal. Delve into the challenges of transmitting indivisible resources through networks, with applications in freight transport and telecommunications. Learn about improving resolution methods for large-scale problems, particularly in satellite constellation management. Examine the dynamic unsplittable flow problem and various solution approaches. Discover a new decomposition method that strengthens linear relaxation, comparing it to classical methods. Gain insights into sequential randomized rounding, mixed integer linear programming, and Dantzig-Wolfe decomposition techniques. Understand the importance of efficient algorithms in managing increasingly large satellite constellations and their impact on industries like telecommunications.

Intro
Presentation summary
A constellation of satellites
A model for unsplittable flows
Sequential randomized rounding
Dynamic unsplittable flows
Algorithms
Mixed integer linear programming
Dantzig-Wolfe decomposition
Dantzig-Wolfe-Fenchel decomposition
An iterative resolution for the separation problem
Conclusion
Future works