Presentation on YouTube.

The problem of transmitting indivisible resources through a network can be found in numerous applications. Indeed, it is useful in industries such as freight transport or telecommunications (optical networks, satellite communications ...). Improving the resolution methods for this problem in terms of resolution speed and quality of the found solution is therefore an important issue. This is especially true in the telecommunication industry where companies tend to build increasingly large constellations of satellites whose management requires increasingly efficient resolution algorithms.

In this talk, we focus on the problem of transmitting user throughput in a constellation of satellites. This problem corresponds to a problem classically studied in the literature under the name of unsplittable flow problem. Although theoretical properties are well known and many resolution approaches exist, the known methods lack efficiency when the problem size is large. To fill this gap we propose algorithms with good performances on large instances of this problem. Moreover, the introduction of constellation dynamics in the problem leads us to focus on the dynamic unsplittable flow problem. As this problem is little studied in the literature, we extend the set of solution methods tested on this problem by proposing different approaches and comparing them experimentally.

Finally, we study decomposition methods able to strengthen the linear relaxation of the unsplittable flow problem. Indeed, this linear relaxation is the basis of most of the solution methods proposed in the literature. The computation of a powerful relaxation is therefore an issue in the resolution of the unsplittable flow problem. We propose a new decomposition method inspired by the two classical methods of the literature.

Biographie : Francois Lamothe is a post-doctoral intern at UQAM, GERAD and CIRRELT working in collaboration with Claudio Contardo and Matthieu Gruson. He finished a PhD at ISAE-Supaero in France where his research focused on flow problems - especially unsplittable flow problems - and decomposition methods. He is now studying the polyhedral structures of set-covering polytopes and related problems.