• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

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
1989
Journal name
European Journal of Operational Research
Volume
41
Number
2
Publisher
Elsevier
Pages
232-239
Publication identifier
http://dx.doi.org/10.1016/0377-2217(89)90389-5
Metadata
Show full item record
Author(s)
Ribeiro, Celso Carneiro
Minoux, Michel
Penna, Manoel Camillo
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 / Keywords
Set partitioning; column generation with ranking; traffic assignment; integer programming

Related items

Showing items related by title and author.

  • Thumbnail
    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é
  • Thumbnail
    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é
  • Thumbnail
    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é
  • Thumbnail
    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é
  • Thumbnail
    The Fair OWA One-to-One Assignment Problem: NP-Hardness and Polynomial Time Special Cases 
    Lesca, Julien; Minoux, Michel; Perny, Patrice (2019) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo