A heuristic procedure based on column generation to solve a cutting stock problem

This paper focuses on a real life cutting stock problem first investigated by Chu and Antonio (1999). In this model, the constraints as well as the objective function are more complex compared with the traditional cutting stock models where some technical parameters are not considered. In this paper, we first apply column generation to this complex cutting stock model. Because of the concavity of the cutting cost with the packet size, the lower bound obtained by column generation is far from reality. This is a new discovery compared with the traditional view: the lower bound obtained by the column generation is tight. To solve the problem, a heuristic procedure is proposed based on this loose lower bound. It is fast and yields the near-optimal solutions. The computational results show that this heuristic procedure based on column generation improves by 10% the performance of the partner company.