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
TypeArticle accepté pour publication ou publié
Journal nameEuropean Journal of Operational Research
MetadataShow full item record
Abstract (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 / KeywordsSet partitioning; column generation with ranking; traffic assignment; integer programming
Showing items related by title and author.
A new approach for crew pairing problems by column generation with an application to air transportation Lavoie, Sylvie; Minoux, Michel; Odier, Edouard (1988) Article accepté pour publication ou publié
Benders decomposition for very large scale partial set covering and maximal covering location problems Cordeau, Jean-François; Furini, Fabio; Ljubić, Ivana (2019) Article accepté pour publication ou publié
A linear expected-time algorithm for deriving all logical conclusions implied by a set of boolean inequalities Hansen, Pierre; Jaumard, Brigitte; Minoux, Michel (1986) Article accepté pour publication ou publié
An efficient algorithm for the transitive closure and a linear worst-case complexity result for a class of sparse graphs Jaumard, Brigitte; Minoux, Michel (1986) Article accepté pour publication ou publié