An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment. (English) Zbl 0679.90043

Ribeiro, Celso Carneiro; Minoux, Michel; Penna, Manoel Camillo

Eur. J. Oper. Res. 41, No. 2, 232-239 (1989).

The paper is devoted to a method of solving some very large-scale set partitioning problems with special structure, such as the matrix decomposition problem. P. C. Gilmore and R. E. Gomory [Oper. Res. 9, 849-859 (1961; Zbl 0096.355)] applied the column generation technique to a class of combinatorial problems to obtain good approximate solutions and lower bounds. In this paper the authors show how the branch-and-bound method can be combined with the column generation technique to ensure obtaining the exact optimal integer solution. They also report extensive computational results.

Reviewer: X.Zhang

MSC:

90C10	Integer programming
90C27	Combinatorial optimization
65K05	Numerical mathematical programming methods
90C06	Large-scale problems in mathematical programming
05C70	Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Keywords:

traffic assignment; large-scale set partitioning; matrix decomposition; column generation technique; approximate solutions; lower bounds; branch- and-bound

Citations:

Zbl 0096.355

References:

[1]	Balas, E.; Landweer, P.R., Traffic assignment in communication satellites, Operations research letters, 2, 141-147, (1983) · Zbl 0526.90065
[2]	Brandt, E., Optimisation de ressources pour des transmissions par satellites utilisant l’ AMRT, ()
[3]	Busacker, R.G.; Gowen, P.J., A procedure for determining a family of minimal cost network flow patterns, ()
[4]	Camerini, P.; Maffioli, F.; Tartara, G., Some scheduling algorithms for SS/TDMA systems, (), 405-409
[5]	Dantzig, G.B.; Orden, A.; Wolfe, P., The generalized simplex method for minimizing a linear form under linear inequality restraints, Pacific journal of mathematics, 5, 183-195, (1955) · Zbl 0064.39402
[6]	Edmonds, J.; Karp, R.M., Theoretical improvements in algorithmic efficiency for network flow problems, Journal of the ACM, 19, 248-264, (1972) · Zbl 0318.90024
[7]	Gilmore, P.C.; Gomory, R.E., A linear programming apporach to the cutting-stock problem, Operations research, 9, 849-859, (1961) · Zbl 0096.35501
[8]	Gopal, I.S., Scheduling algorithms for multi-beam communication satellites, ()
[9]	Gopal, I.S.; Wong, C.K., Minimizing the number of switching in an SS/TDMA system, ()
[10]	Inukai, T., Comments on ‘analysis of a switch matrix for an SS/TDMA systems’, (), 1669-1670
[11]	Inukai, T., An efficient SS/TDMA time slot assignment algorithm, IEEE transactions on communications, 27, 1449-1455, (1979)
[12]	Ito, Y.; Urano, Y.; Muratani, T.; Yamaguchi, M., Analysis of a switch matrix for an SS?TDMA system, (), 411-419
[13]	Lawler, E.L., Procedure for computing the k-best solutions to discrete optimization problems and its applications to shortest path problem, Management science, 18, 401-405, (1972) · Zbl 0234.90050
[14]	Minoux, M., Optimal traffic assignment in an SS/TDMA frame: A new approach by set covering and column generation, RAIRO recherche opérationnelle, 20, 1-13, (1986) · Zbl 0608.90076
[15]	Minoux, M., A class of combinatorial problems with polynomially solvable large scale scale set covering/set partitioning relaxations, RAIRO recherche opérationnelle, 21, 105-136, (1987) · Zbl 0644.90061
[16]	Murty, K.G., An algorithm for ranking all the assignments in order of increasing cost, Operations research, 16, 682-687, (1968) · Zbl 0214.18705
[17]	Murty, K.G., Linear and combinatorial programming, (1976), Wiley New York · Zbl 0634.90037
[18]	Rendl, F., On the complexity of decomposing matrices arising in satellite communications, Operations research letters, 4, 5-8, (1985) · Zbl 0569.90064
[19]	Rendl, F. (1986), Private Communication.
[20]	Vismara, L., Piano di accesso dei messaggi in sistemi SS/TDMA: un metodo di enumerazione implicita per minimizzare il tempo di transmissione, (1982), Tesi di Laurea, Politecnico di Milano, Dipartimento di Elettronica, (Paolo Camerini i Francesco Maffioli, relatori)
[21]	Yen, J.Y., Finding the k-shortest loopless paths in a network, Management science, 17, 712-716, (1971) · Zbl 0218.90063