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

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.