Download PDF - A branch&bound algorithm for solving one-dimensional cutting stock problems exactlyAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

A branch&bound algorithm for solving one-dimensional cutting stock problems exactly

Authors 1, 1

Affiliations

  1. Institute of Numerical Mathematics, Technical University Dresden, Mommsenstr. 13, D-01062 Dresden, Germany

Abstract

Many numerical computations reported in the literature show only a small difference between the optimal value of the one-dimensional cutting stock problem (1CSP) and that of the corresponding linear programming relaxation. Moreover, theoretical investigations have proven that this difference is smaller than 2 for a wide range of subproblems of the general 1CSP.

Keywords

ENG
rounding, cutting stock problem, branch&bound, integer optimization

Bibliography

  1. S. Baum and L. E. Trotter, Jr., Integer rounding for polymatroid and branching optimization problems, SIAM J. Algebraic Discrete Methods 2 (1981), 416-425.
  2. E. G. Coffmann, Jr., M. R. Garey, D. S. Johnson and R. E. Targon, Performance bounds for level oriented two-dimensional packing algorithms, SIAM J. Comput. 9 (1980), 808-826.
  3. A. Diegel, Integer LP solution for large trim problem, Working Paper, University of Natal, South Africa, 1988.
  4. H. Dyckhoff and U. Finke, Cutting and Packing in Production and Distribution, Physica Verlag, Heidelberg, 1992.
  5. M. Fieldhouse, The duality gap in trim problems, SICUP-Bulletin No. 5, 1990.
  6. P. C. Gilmore and R. E. Gomory, A linear programming approach to the cutting stock problem, Oper. Res. 9 (1961), 849-859.
  7. P. C. Gilmore and R. E. Gomory, A linear programming approach to the cutting stock problem, II, ibid. 11 (1963), 863-888.
  8. R. E. Johnston, Rounding algorithms for cutting stock problems, Asia-Pacific J. Oper. Res. 3 (1986), 166-171.
  9. O. Marcotte, The cutting stock problem and integer rounding, Math. Programming 33 (1985), 82-92.
  10. O. Marcotte, An instance of the cutting stock problem for which the rounding property does not hold, Oper. Res. Lett. 4 (1986), 239-243.
  11. G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Optimization, Wiley, New York, 1988.
  12. G. Scheithauer and J. Terno, About the gap between the optimal values of the integer and continuous relaxation one-dimensional cutting stock problem, in: Operations Research Proceedings 1991, Springer, Berlin, 1992, 439-444.
  13. G. Scheithauer and J. Terno, The modified integer round-up property for the one-dimensional cutting stock problem, Preprint MATH-NM-10-1993, TU Dresden (submitted).
  14. G. Scheithauer and J. Terno, Theoretical investigations on the modified integer round-up property for one-dimensional cutting stock problem, Preprint MATH-NM-12-1993, TU Dresden (submitted).
  15. G. Scheithauer and J. Terno, Equivalence of cutting stock problems, Working Paper, TU Dresden, 1993.
  16. J. Terno, R. Lindemann und G. Scheithauer, Zuschnittprobleme und ihre praktische Lösung, Verlag Harry Deutsch, Thun und Frankfurt/Main, und Fachbuchverlag, Leipzig, 1987.
  17. G. Wäscher and T. Gau, Two approaches to the cutting stock problem, IFORS '93 Conference, Lisboa 1993.
Applicationes Mathematicae
1995-1996/23/2
Export to PBN, Opens in new tab
Pages:
151-167
Main language of publication
English
Received
1994-05-05
Published
1995
Exact and natural sciences