Comparison of Bundle and Classical Column Generation
LEMARÉCHAL, Claude
Modelling, Simulation, Control and Optimization of Non-Smooth Dynamical Systems [BIPOP]
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]
See more >
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
LEMARÉCHAL, Claude
Modelling, Simulation, Control and Optimization of Non-Smooth Dynamical Systems [BIPOP]
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]
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
MICHEL, Sophie
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Laboratoire de Mathématiques Appliquées du Havre [LMAH]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Laboratoire de Mathématiques Appliquées du Havre [LMAH]
VANDERBECK, François
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
< Reduce
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Language
en
Article de revue
This item was published in
Mathematical Programming. 2008-06, vol. 113, n° 2, p. 299-344
Springer Verlag
English 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 ...Read more >
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.Read less <
English Keywords
Nonsmooth convex optimization
Volume algorithm
Bundle algorithm
Cutting-plane algorithms
Stabilized column generation
Dantzig-Wolfe decomposition
Lagrangian duality
Origin
Hal imported