An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment

This paper shows how branch-and-bound and column generation techniques can be combined 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 systems optimization. The main contribution of the present 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.