An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment
Ribeiro, Celso Carneiro; Minoux, Michel; Penna, Manoel Camillo (1989), An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment, European Journal of Operational Research, 41, 2, p. 232-239. http://dx.doi.org/10.1016/0377-2217(89)90389-5
Type
Article accepté pour publication ou publiéDate
1989Journal name
European Journal of Operational ResearchVolume
41Number
2Publisher
Elsevier
Pages
232-239
Publication identifier
Metadata
Show full item recordAbstract (EN)
We show in this paper how branch-and-bound and column generation techniques can be conbined very efficiently to solve to optimality some very large scale set partitioning problems with special structure, such as the matrix decomposition problem arising in the context of satellite communication system optimization. The main contribution of our approach is the use of column generation during the tree search procedure, combined with a ranking procedure which ensures that the exact optimal integer solution is obtained. Extensive computational experiments are reported for the matrix decomposition problem encountered in the search for optimal schedules in satellite switching systems, showing the effectiveness of this approach.Subjects / Keywords
Set partitioning; column generation with ranking; traffic assignment; integer programmingRelated items
Showing items related by title and author.
-
Lavoie, Sylvie; Minoux, Michel; Odier, Edouard (1988) Article accepté pour publication ou publié
-
Cordeau, Jean-François; Furini, Fabio; Ljubić, Ivana (2019) Article accepté pour publication ou publié
-
Hansen, Pierre; Jaumard, Brigitte; Minoux, Michel (1986) Article accepté pour publication ou publié
-
Jaumard, Brigitte; Minoux, Michel (1986) Article accepté pour publication ou publié
-
Lesca, Julien; Minoux, Michel; Perny, Patrice (2019) Article accepté pour publication ou publié