# 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

## Access Full Article

top## Abstract

top## How to cite

topScheithauer, 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] 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] 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. Zbl0096.35501
- [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] R. E. Johnston, Rounding algorithms for cutting stock problems, Asia-Pacific J. Oper. Res. 3 (1986), 166-171. Zbl0616.90044
- [9] O. Marcotte, The cutting stock problem and integer rounding, Math. Programming 33 (1985), 82-92. Zbl0584.90063
- [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] G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Optimization, Wiley, New York, 1988. Zbl0652.90067
- [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). Zbl0890.90147
- [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] G. Scheithauer and J. Terno, Equivalence of cutting stock problems, Working Paper, TU Dresden, 1993. Zbl0818.90083
- [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] G. Wäscher and T. Gau, Two approaches to the cutting stock problem, IFORS '93 Conference, Lisboa 1993. Zbl0918.90117

## NotesEmbed ?

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