×

zbMATH — the first resource for mathematics

Branch-and-price algorithms for the one-dimensional cutting stock problem. (English) Zbl 0897.90161
Summary: We compare two branch-and-price approaches for the cutting stock problem. Each algorithm is based on a different integer programming formulation of the column generation master problem. One formulation results in a master problem with 0-1 integer variables while the other has general integer variables. Both algorithms employ column generation for solving LP relaxations at each node of a branch-and-bound tree to obtain optimal integer solutions. These different formulations yield the same column generation subproblem, but require different branch-and-bound approaches. Computational results for both real and randomly generated test problems are presented.

MSC:
90C27 Combinatorial optimization
90C05 Linear programming
90B30 Production models
90C09 Boolean programming
Software:
MINTO
PDF BibTeX XML Cite
Full Text: DOI