Skip to Main content Skip to Navigation
Journal articles

An inexact bundle variant suited to column generation

Krzysztof C. Kiwiel Claude Lemaréchal 1 
1 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
Abstract : We give a bundle method for constrained convex optimization. Instead of using penalty functions, it shifts iterates towards feasibility, by way of a Slater point, assumed to be known. Besides, the method accepts an oracle delivering function and subgradient values with unknown accuracy. Our approach is motivated by a number of applications in column generation, in which constraints are positively homogeneous--so that zero is a natural Slater point--and an exact oracle may be time consuming. Finally, our convergence analysis employs arguments which have been little used so far in the bundle community. The method is illustrated on a number of cutting-stock problems.
Document type :
Journal articles
Complete list of metadata
Contributor : Brigitte Bidégaray-Fesquet Connect in order to contact the contributor
Submitted on : Thursday, May 9, 2013 - 2:06:28 PM
Last modification on : Thursday, January 20, 2022 - 5:30:58 PM

Links full text




Krzysztof C. Kiwiel, Claude Lemaréchal. An inexact bundle variant suited to column generation. Mathematical Programming, Springer Verlag, 2009, 118 (1), pp.177-206. ⟨10.1007/s10107-007-0187-4⟩. ⟨hal-00821373⟩



Record views