Skip to Main content Skip to Navigation
Journal articles

Comparison of Bundle and Classical Column Generation

Olivier Briant 1 Claude Lemaréchal 2 Philippe Meurdesoif 3, 4 Sophie Michel 4, 5 Nancy Perrot François Vanderbeck 3, 4
1 G-SCOP_OC - Optimisation Combinatoire
G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production
2 BIPOP - Modelling, Simulation, Control and Optimization of Non-Smooth Dynamical Systems
Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann, Grenoble INP - Institut polytechnique de Grenoble - Grenoble Institute of Technology
4 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 : 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 comparisons are presented for five applications: cutting stock (which includes bin packing), vertex coloring, capacitated vehicle routing, multi-item lot sizing, and traveling salesman. We also give a sketchy comparison with the volume algorithm.
Document type :
Journal articles
Complete list of metadata
Contributor : François Vanderbeck Connect in order to contact the contributor
Submitted on : Thursday, November 27, 2008 - 3:46:21 PM
Last modification on : Saturday, April 2, 2022 - 3:10:16 AM

Links full text



Olivier Briant, Claude Lemaréchal, Philippe Meurdesoif, Sophie Michel, Nancy Perrot, et al.. Comparison of Bundle and Classical Column Generation. Mathematical Programming, Springer Verlag, 2008, 113 (2), pp.299-344. ⟨10.1007/s10107-006-0079-z⟩. ⟨inria-00342510⟩



Record views