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

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


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.)


Zbl 0096.355
Full Text: DOI


[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.