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

Artur Pessoa 1 Ruslan Sadykov 1, 2 Eduardo Uchoa 1 François Vanderbeck 1, 2, *
* Auteur correspondant
1 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
Abstract : 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 strategy that makes 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.
Type de document :
Communication dans un congrès
Vincenzo Bonifaci and Camil Demetrescu and Alberto Marchetti-Spaccamela. 12th International Symposium on Experimental Algorithms, Jun 2013, Rome, Italy. Sringer, LNCS 7933, pp.354-365, 2013, June 2013. 〈http://www.springer.com/computer/theoretical+computer+science/book/978-3-642-38526-1〉. 〈10.1007/978-3-642-38527-8〉
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00750412
Contributeur : François Vanderbeck <>
Soumis le : mercredi 27 mars 2013 - 13:00:01
Dernière modification le : jeudi 11 janvier 2018 - 06:22:12

Fichier

stabShortPaper3.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Artur Pessoa, Ruslan Sadykov, Eduardo Uchoa, François Vanderbeck. In-Out Separation and Column Generation Stabilization by Dual Price Smoothing. Vincenzo Bonifaci and Camil Demetrescu and Alberto Marchetti-Spaccamela. 12th International Symposium on Experimental Algorithms, Jun 2013, Rome, Italy. Sringer, LNCS 7933, pp.354-365, 2013, June 2013. 〈http://www.springer.com/computer/theoretical+computer+science/book/978-3-642-38526-1〉. 〈10.1007/978-3-642-38527-8〉. 〈hal-00750412v3〉

Partager

Métriques

Consultations de la notice

753

Téléchargements de fichiers

266