HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

Comparison of Bundle and Classical Column Generation

Abstract : When a column generation approach is applied to decomposable mixed integer programming problems, it is standard to formulate and solve the master problem as a linear program. Seen in the dual space, this results in the algorithm known in the nonlinear programming community as the cutting-plane algorithm of Kelley and Cheney-Goldstein. However, more stable methods with better theoretical convergence rates are known and have been used as alternatives to this standard. One of them is the bundle method; our aim is to illustrate its differences with Kelley's method. In the process we review alternative stabilization techniques used in column generation, comparing them from both primal and dual points of view. Numerical comparaisons are presented for five applications: cutting stock (which includes bin packing), vertex coloring, capacitated vehicle routing, multi-item lot sizing, and traveling salesman.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00070554
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Friday, May 19, 2006 - 8:50:35 PM
Last modification on : Thursday, January 20, 2022 - 4:15:04 PM
Long-term archiving on: : Sunday, April 4, 2010 - 9:27:37 PM

Identifiers

  • HAL Id : inria-00070554, version 1

Collections

Citation

O. Briant, C. Lemaréchal, Ph. Meurdesoif, S. Michel, N. Perrot, et al.. Comparison of Bundle and Classical Column Generation. [Research Report] RR-5453, INRIA. 2005, pp.31. ⟨inria-00070554⟩

Share

Metrics

Record views

167

Files downloads

346