Optimal traffic assignment in SS/TDMA frame: A new approach by set covering and column generation

The paper addresses here the problem of optimal assignment of a given traffic matrix, within a satellite system TDMA (time division multiple access) frame where no traffic splitting is allowed (in view of keeping the number of different switching states as low as possible). After reformulating the problem as a large scale set covering problem, it is shown that, in spite of the large number of columns, its continuous relaxation can be solved optimally according to a column-generation procedure (generalized linear programming). Computational experiments show that this approach usually produces lower bounds which significantly improve upon the trivial lower bounds used so far for this problem (the greatest row or column sum of the traffic matrix) thus opening the way to exact solution of problems of higher dimensions.