We consider the capacitated lot sizing problem with multiple items, setup time and unrelated parallel machines, and apply Dantzig–Wolfe decomposition to a strong reformulation of the problem. Unlike in the traditional approach where the linking constraints are the capacity constraints, we use the flow constraints, i.e. the demand constraints, as linking constraints. The aim of this approach is to obtain high quality lower bounds. We solve the master problem applying two solution methods that combine Lagrangian relaxation and Dantzig–Wolfe decomposition in a hybrid form. A primal heuristic, based on transfers of production quantities, is used to generate feasible solutions. Computational experiments using data sets from the literature are presented and show that the hybrid methods produce lower bounds of excellent quality and competitive upper bounds, when compared with the bounds produced by other methods from the literature and by a high-performance MIP software.Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)Natural Sciences and Engineering Research Council of CanadaUniversidade Estadual Paulista Júlio de Mesquita Filho, Departamento de Matemática Aplicada, Instituto de Biociências Letras e Ciências Exatas de São José do Rio Preto, Sao Jose do Rio Preto, Rua Cristóvão Colombo, 2265 (DCCE), Jardim Nazareth, CEP 15054-000, SP, BrasilHEC Montréal and CIRRELT, Canada H3T 2A7 QC, CanadaUniversidade Estadual Paulista Júlio de Mesquita Filho, Departamento de Matemática Aplicada, Instituto de Biociências Letras e Ciências Exatas de São José do Rio Preto, Sao Jose do Rio Preto, Rua Cristóvão Colombo, 2265 (DCCE), Jardim Nazareth, CEP 15054-000, SP, BrasilFAPESP: 2010/16727-9FAPESP: 2013/00965-6FAPESP:2011/22647-0Natural Sciences and Engineering Research Council of Canada: 342182-09