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, (Thèse de 3éme Cycle (1982), Université de Paris-Sud Orsay: Université de Paris-Sud Orsay Paris)
[3] Busacker, R. G.; Gowen, P. J., A procedure for determining a family of minimal cost network flow patterns, (O.R.O. Technical Report 15 (1961), Johns Hopkins University)
[4] Camerini, P.; Maffioli, F.; Tartara, G., Some scheduling algorithms for SS/TDMA systems, (Proceedings of the V International Conference on Digital Satellite Communications. Proceedings of the V International Conference on Digital Satellite Communications, Genoa (1981)), 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, (Ph.D. Dissertation (1982), Columbia University: Columbia University New York)
[9] Gopal, I. S.; Wong, C. K., Minimizing the number of switching in an SS/TDMA system, (Proceedings of the International Symposium on Satellite and Computer Communications. Proceedings of the International Symposium on Satellite and Computer Communications, Versailles (1983))
[10] Inukai, T., Comments on ‘Analysis of a switch matrix for an SS/TDMA systems’, (Proceedings of the IEEE, 66 (1978)), 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, (Proceedings of the IEEE, 65 (1977)), 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: 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.; 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.