Automation and combination of linear-programming based stabilization techniques in column generation - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2014

Automation and combination of linear-programming based stabilization techniques in column generation

Résumé

The convergence of a column generation algorithm can be improved in practice by using so-called stabilization techniques. Proximal methods based on penalising the deviation from the incumbent dual solution have become standards of the domain. However, the analysis of such methods is important to understand the mechanism on which they rely, to appreciate the difference between methods, and to derive intelligent schemes to adjust their parameters. As stabilization procedures for column generation can be viewed as cutting plane strategies in the dual problem, the link with cutting plane separation strategies can be exploited to enlarge the scope of methods and to refine their analysis. Here, we focus on stabilization schemes that rely solely on a linear programming (LP) solver for the column generation master program. This restrictive scope captures the most common implementations where one uses an LP solver to handle the master program. For dual price smoothing techniques, we analyse the link with the in-out separation strategy and we derive generic convergence properties. For penalty function methods as well as for smoothing, we describe proposals for parameter self-adjusting schemes. Such schemes make initial parameter tuning less of an issue as corrections are made. Also, the dynamic adjustments, compared to a static setting, allows to adapt the parameters to the phase of the algorithm. We provide extensive test reports that highlight the comparative performances of such scheme and validate our self-adjusting parameter scheme. Furthermore, our results show that using smoothing in combination with penalty function yields a cumulative effect on convergence speed-ups.
Fichier principal
Vignette du fichier
stabPapWP.pdf (618.18 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01077984 , version 1 (27-10-2014)
hal-01077984 , version 2 (06-08-2015)
hal-01077984 , version 3 (03-01-2017)
hal-01077984 , version 4 (18-05-2017)

Identifiants

  • HAL Id : hal-01077984 , version 1

Citer

A Pessoa, R Sadykov, E Uchoa, F Vanderbeck. Automation and combination of linear-programming based stabilization techniques in column generation. 2014. ⟨hal-01077984v1⟩
886 Consultations
1626 Téléchargements

Partager

Gmail Facebook X LinkedIn More