Abstract (EN)

We show in this paper how branch-and-bound and column generation techniques can be conbined very efficiently to solve to optimality some very large scale set partitioning problems with special structure, such as the matrix decomposition problem arising in the context of satellite communication system optimization. The main contribution of our approach is the use of column generation during the tree search procedure, combined with a ranking procedure which ensures that the exact optimal integer solution is obtained. Extensive computational experiments are reported for the matrix decomposition problem encountered in the search for optimal schedules in satellite switching systems, showing the effectiveness of this approach.