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

Minoux, M.

RAIRO, Rech. Opér. 20, 273-285 (1986).

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.

MSC:

90C27	Combinatorial optimization
65K05	Numerical mathematical programming methods
90C05	Linear programming

Keywords:

optimal assignment; traffic matrix; satellite system; time division multiple access; large scale set covering problem; continuous relaxation; column-generation procedure; Computational experiments