In-Out Separation and Column Generation Stabilization by Dual Price Smoothing - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2012

In-Out Separation and Column Generation Stabilization by Dual Price Smoothing

Résumé

Stabilization procedures for column generation can be viewed as cutting plane strategies in the dual. Exploiting the link between in-out separation strategies and dual price smoothing techniques for column generation, we derive a generic bound convergence property for algorithms using a smoothing feature. Such property adds to existing in-out asymptotic convergence results. Beyond theoretically convergence, we describe a proposal for effective finite convergence in practice and we develop a smoothing auto-regulating strategies that make the need for parameter tuning obsolete. These contributions turn stabilization by smoothing into a general purpose practical scheme that can be used into a generic column generation procedure. We conclude the paper by showing that the approach can be combined with an ascent method, leading to improved performances. Such combination might inspire novel cut separation strategies.
Fichier principal
Vignette du fichier
stabShortPaper2.pdf (505.42 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00750412 , version 1 (01-02-2013)
hal-00750412 , version 2 (09-02-2013)
hal-00750412 , version 3 (27-03-2013)

Identifiants

  • HAL Id : hal-00750412 , version 1

Citer

Artur Alves Pessoa, Ruslan Sadykov, Eduardo Uchoa, François Vanderbeck. In-Out Separation and Column Generation Stabilization by Dual Price Smoothing. [Research Report] 2012. ⟨hal-00750412v1⟩
389 Consultations
1172 Téléchargements

Partager

Gmail Facebook X LinkedIn More