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

Guided by the Cutting Stock Problem (CSP) this paper studies how features like cutting planes, rounding heuristics, early branching and variable fixing can be incorporated in a branch and price (column generation) algorithm. In particular it is shown that a lower bound provided by the LP relaxation of a column generation formulation of the CSP dominates combinatorial bounds. This leads to a new pseudopolynomial heuristic for the CSP. The author discusses in detail the branching scheme and other implementational details for branch and price algorithms. A computational study on bin packing and cutting stock problems reveals the effects of various algorithmic settings and shows the efficiency of the resulting algorithm for these problem classes.