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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.