Optimal traffic assignment in an SS/TDMA frame: A new approach by set covering and column generation. (English) Zbl 0608.90076

We address 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 an exact solution of problems of higher dimensions.


90C27 Combinatorial optimization
65K05 Numerical mathematical programming methods
90C05 Linear programming
Full Text: DOI EuDML