BRIANT, Olivier; LEMARÉCHAL, Claude; MEURDESOIF, Philippe; MICHEL, Sophie; PERROT, Nancy; VANDERBECK, François

doi:10.1007/s10107-006-0079-z

Métadonnées

Afficher la notice complète

Licence d’utilisation du document

BRIANT, Olivier
Optimisation Combinatoire [G-SCOP_OC]

LEMARÉCHAL, Claude
Modelling, Simulation, Control and Optimization of Non-Smooth Dynamical Systems [BIPOP]

MEURDESOIF, Philippe
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]

Langue

Article de revue

Ce document a été publié dans

Mathematical Programming. 2008-06, vol. 113, n° 2, p. 299-344

Springer Verlag

Résumé en anglais

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.< Réduire

Mots clés en anglais

Nonsmooth convex optimization

Volume algorithm

Bundle algorithm

Cutting-plane algorithms

Stabilized column generation

Dantzig-Wolfe decomposition

Lagrangian duality

Métadonnées

Partager cette publication !

Licence d’utilisation du document

Comparison of Bundle and Classical Column Generation

Langue

Ce document a été publié dans

Résumé en anglais

Mots clés en anglais

URI

DOI

Origine

Unités de recherche