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 based column generation for the cutting stock problem. The main focus of research is study extend which standard branch-and-bound enhancement features such as variable fixing, tightening formulation with planes, early branching, and rounding heuristics can be usefully incorporated in a branch-and-price algorithm. We review compare lower bounds propose pseudo-polynomial heuristic. discuss implementation important integer programming and, particular, branching scheme. Our computational results demonstrate efficiency resulting various classes bin packing problems.