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

Guntram Scheithauer; Johannes Terno

Applicationes Mathematicae (1995)

  • Volume: 23, Issue: 2, page 151-167
  • ISSN: 1233-7234

Abstract

top
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.

How to cite

top

Scheithauer, Guntram, and Terno, Johannes. "A branch&bound algorithm for solving one-dimensional cutting stock problems exactly." Applicationes Mathematicae 23.2 (1995): 151-167. <http://eudml.org/doc/219122>.

@article{Scheithauer1995,
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.},
author = {Scheithauer, Guntram, Terno, Johannes},
journal = {Applicationes Mathematicae},
keywords = {rounding; cutting stock problem; branch&bound; integer optimization; one-dimensional cutting stock; branch-and-bound},
language = {eng},
number = {2},
pages = {151-167},
title = {A branch&bound algorithm for solving one-dimensional cutting stock problems exactly},
url = {http://eudml.org/doc/219122},
volume = {23},
year = {1995},
}

TY - JOUR
AU - Scheithauer, Guntram
AU - Terno, Johannes
TI - A branch&bound algorithm for solving one-dimensional cutting stock problems exactly
JO - Applicationes Mathematicae
PY - 1995
VL - 23
IS - 2
SP - 151
EP - 167
AB - 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.
LA - eng
KW - rounding; cutting stock problem; branch&bound; integer optimization; one-dimensional cutting stock; branch-and-bound
UR - http://eudml.org/doc/219122
ER -

References

top
  1. [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. Zbl0518.90058
  2. [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. [3] A. Diegel, Integer LP solution for large trim problem, Working Paper, University of Natal, South Africa, 1988. 
  4. [4] H. Dyckhoff and U. Finke, Cutting and Packing in Production and Distribution, Physica Verlag, Heidelberg, 1992. 
  5. [5] M. Fieldhouse, The duality gap in trim problems, SICUP-Bulletin No. 5, 1990. 
  6. [6] P. C. Gilmore and R. E. Gomory, A linear programming approach to the cutting stock problem, Oper. Res. 9 (1961), 849-859. Zbl0096.35501
  7. [7] P. C. Gilmore and R. E. Gomory, A linear programming approach to the cutting stock problem, II, ibid. 11 (1963), 863-888. Zbl0124.36307
  8. [8] R. E. Johnston, Rounding algorithms for cutting stock problems, Asia-Pacific J. Oper. Res. 3 (1986), 166-171. Zbl0616.90044
  9. [9] O. Marcotte, The cutting stock problem and integer rounding, Math. Programming 33 (1985), 82-92. Zbl0584.90063
  10. [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. Zbl0598.90066
  11. [11] G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Optimization, Wiley, New York, 1988. Zbl0652.90067
  12. [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. [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). Zbl0890.90147
  14. [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). Zbl0890.90147
  15. [15] G. Scheithauer and J. Terno, Equivalence of cutting stock problems, Working Paper, TU Dresden, 1993. Zbl0818.90083
  16. [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. Zbl0657.65089
  17. [17] G. Wäscher and T. Gau, Two approaches to the cutting stock problem, IFORS '93 Conference, Lisboa 1993. Zbl0918.90117

NotesEmbed ?

top

You must be logged in to post comments.