Combining dual price smoothing and piecewise linear penalty function stabilization in column generation: experimental results

Ruslan Sadykov 1, 2 Artur Alves Pessoa 3 Eduardo Uchoa 3 François Vanderbeck 1, 2
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 : Column generation is a well-known method to solve large-scale combinatorial optimisation problem. However, its application in practice if often limited by convergence issues. To overcome this drawback, several stabilization techniques have been proposed. Probably, the most common techniques are 1) adding piecewise linear penalty functions to the dual objective and 2) dual price smoothing, which consists in pricing with a linear combination of the current dual solution and the best dual solution obtained earlier. Recently we proposed an automatic (parameter-less) variant of the dual price smoothing technique. In this work, we experimentally compare efficiency of the two mentioned stabilisation techniques on a wide range of problems, including machine scheduling, generalised assignment, lot sizing, capacitated vehicle routing, shift scheduling, and min-cost multi-commodity flow. Then, we also test numerically the combination of these techniques. Our experimental results show that for most problems this combination outperforms the two techniques applied separately.
Type de document :
Communication dans un congrès
3rd International Symposium on Combinatorial Optimization ISCO'2014, Mar 2014, Lisbon, Portugal
Liste complète des métadonnées

https://hal.inria.fr/hal-01104948
Contributeur : Ruslan Sadykov <>
Soumis le : lundi 19 janvier 2015 - 15:01:13
Dernière modification le : jeudi 11 janvier 2018 - 06:22:12

Identifiants

  • HAL Id : hal-01104948, version 1

Citation

Ruslan Sadykov, Artur Alves Pessoa, Eduardo Uchoa, François Vanderbeck. Combining dual price smoothing and piecewise linear penalty function stabilization in column generation: experimental results. 3rd International Symposium on Combinatorial Optimization ISCO'2014, Mar 2014, Lisbon, Portugal. 〈hal-01104948〉

Partager

Métriques

Consultations de la notice

301