EconPapers    
Economics at your fingertips  
 

Automation and Combination of Linear-Programming Based Stabilization Techniques in Column Generation

A. Pessoa (artur@producao.uff.br), R. Sadykov (ruslan.sadykov@inria.fr), E. Uchoa (uchoa@producao.uff.br) and F. Vanderbeck (fv@math.u-bordeaux.fr)
Additional contact information
A. Pessoa: LOGIS Lab, Universidade Federal Fluminense, Niterói 24210-510, Brazil
R. Sadykov: Inria Bordeaux-Sud-Ouest, Talence 33405, France; and Mathematics Institute, University of Bordeaux, Talence 33405, France
E. Uchoa: LOGIS Lab, Universidade Federal Fluminense, Niterói 24210-510, Brazil
F. Vanderbeck: Inria Bordeaux-Sud-Ouest, Talence 33405, France; and Mathematics Institute, University of Bordeaux, Talence 33405, France

INFORMS Journal on Computing, 2018, vol. 30, issue 2, 339-360

Abstract: The convergence of a column generation algorithm can be improved in practice by using stabilization techniques. Smoothing and proximal methods based on penalizing the deviation from the incumbent dual solution have become standards of the domain. Interpreting column generation as cutting plane strategies in the dual problem, we analyze the mechanisms on which stabilization relies. In particular, the link is established between smoothing and in-out separation strategies to 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 dynamically. Such adjustments also allow us to adapt the parameters to the phase of the algorithm. We provide extensive test reports that validate our self-adjusting parameter scheme and highlight their performances. Our results also show that using smoothing in combination with a penalty function yields a cumulative effect on convergence speed-ups.

Keywords: column generation; stabilization; cutting plane separation (search for similar items in EconPapers)
Date: 2018
References: Add references at CitEc
Citations: View citations in EconPapers (30)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2017.0784 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:30:y:2018:i:2:p:339-360

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher (casher@informs.org).

 
Page updated 2024-12-28
Handle: RePEc:inm:orijoc:v:30:y:2018:i:2:p:339-360