Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
C. Barnhart, C., E.L. Johnson, G.L. Nemhauser, M.W.P. Savelsbergh, and P.H. Vance, “Branch-and-Price: Column Generation for Solving Huge Integer Programs”, Operations Research, to appear.
M. Desrochers, and F. Soumis, “A Column Generation Approach to the Urban Transit Crew Scheduling Problem”, Transportation Science, vol. 23, pp. 1–13, 1989.
J. Desrosiers, P. Hansen, B. Jaumard, F. Soumis, and D. Villeneuve, Dantzig-Wolfe Decomposition and Column Generation for Integer and Non-convex Programming, Working Paper, Ecole des Hautes Etudes Commerciales, Montreal, 1996.
A.A. Farley, “A Note on Bounding a Class of Linear Programming Problems Including Cutting Stock Problems”, Operations Research, vol. 38, pp. 922–923, 1990.
P.C. Gilmore and R.E. Gomory, “A Linear Programming Approach to the Cutting-Stock Problem”, Operations Research, vol. 9, pp. 849–859, 1961.
C. Goulimis, “Optimal Solutions for the Cutting Stock Problem,” European Journal of Operational Research, vol. 44, pp. 197–208, 1990.
E. Horowitz and S. Sahni, “Computing Partitions with Applications to the Knapsack Problem,” Journal of ACM, vol. 21, pp. 77–292, 1974.
E.L. Johnson, “Modeling and Strong Linear Programs for Mixed Integer Programming”, in S.W. Wallace (ed.), Algorithms and Model Formulations in Mathematical Programming, Berlin: Springer-Verlag, pp. 1–43, 1989.
O. Marcotte, “The Cutting Stock Problem and Integer Rounding”, Mathematical Programming, vol. 33, pp. 82–92, 1985.
M. Parker and J. Ryan, ”A column generation algorithm for bandwidth packing,” Telecommunications Systems, to appear.
D.M. Ryan, and B.A. Foster, An integer programming approach to scheduling, in A. Wren (ed.), Computer Scheduling of Public Transport Urban Passenger Vehicle and Crew Scheduling, Amsterdam: North-Holland, pp. 269–280, 1981.
M.W.P. Savelsbergh, G.C. Sigismondi, and G.L. Nemhauser, “A Functional Description of MINTO, A Mixed INTeger Optimizer”, Technical Report, Computational Optimization Center, Institute of Technology, Atlanta, Georgia, 1992.
M.W.P. Savelsbergh, ”A Branch-and-Price Algorithm for the Generalized Assignment Problem,” Operations Research, to appear.
P.H. Vance, C. Barnhart, E.L. Johnson, and G.L. Nemhauser, “Solving Binary Cutting Stock Problems by Column Generation and Branch-and-Bound” Computational Optimization and Applications, vol. 3, pp. 111–130, 1994.
F. Vanderbeck and L.A. Wolsey, ”An Exact Algorithm for IP Column Generation,” Technical Report, CORE, 1994.
G. Wascher and T. Gau, ”Generating Almost Optimal Solutions for the Integer One-dimensional Cutting Stock Problem,” Arbeitsbericht-Nr. 94/06, Technischen Universitat Braunschweig, Braunschweig, Germany, 1994.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Vance, P.H. Branch-and-Price Algorithms for the One-Dimensional Cutting Stock Problem. Computational Optimization and Applications 9, 211–228 (1998). https://doi.org/10.1023/A:1018346107246
Issue Date:
DOI: https://doi.org/10.1023/A:1018346107246