Computational study of a column generation algorithm for bin packing and cutting stock problems

This paper reports on our attempt to design an efficient exact algorithm ba sed on column generation for the cutting stock problem. The main focus of t he research is to study the extend to which standard branch-and-bound enhan cement features such as variable fixing, the tightening of the formulation with cutting planes, early branching, and rounding heuristics can be useful ly incorporated in a branch-and-price algorithm. We review and compare lowe r bounds for the cutting stock problem. We propose a pseudo-polynomial heur istic. We discuss the implementation of the important features of the integ er programming column generation algorithm and, in particular, the implemen tation of the branching scheme. Our computational results demonstrate the e fficiency of the resulting algorithm for Various classes of bin packing and cubing stack problems.