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.
@article{bwmeta1.element.bwnjournal-article-zmv23i2p151bwm,
author = {Guntram Scheithauer and Johannes Terno},
title = {A branch\&bound algorithm for solving one-dimensional cutting stock problems exactly},
journal = {Applicationes Mathematicae},
volume = {23},
year = {1995},
pages = {151-167},
zbl = {0831.90091},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-zmv23i2p151bwm}
}
Scheithauer, Guntram; Terno, Johannes. A branch&bound algorithm for solving one-dimensional cutting stock problems exactly. Applicationes Mathematicae, Tome 23 (1995) pp. 151-167. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-zmv23i2p151bwm/
[000] [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. | Zbl 0518.90058
[001] [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.
[002] [3] A. Diegel, Integer LP solution for large trim problem, Working Paper, University of Natal, South Africa, 1988.
[003] [4] H. Dyckhoff and U. Finke, Cutting and Packing in Production and Distribution, Physica Verlag, Heidelberg, 1992.
[004] [5] M. Fieldhouse, The duality gap in trim problems, SICUP-Bulletin No. 5, 1990.
[005] [6] P. C. Gilmore and R. E. Gomory, A linear programming approach to the cutting stock problem, Oper. Res. 9 (1961), 849-859. | Zbl 0096.35501
[006] [7] P. C. Gilmore and R. E. Gomory, A linear programming approach to the cutting stock problem, II, ibid. 11 (1963), 863-888. | Zbl 0124.36307
[007] [8] R. E. Johnston, Rounding algorithms for cutting stock problems, Asia-Pacific J. Oper. Res. 3 (1986), 166-171. | Zbl 0616.90044
[008] [9] O. Marcotte, The cutting stock problem and integer rounding, Math. Programming 33 (1985), 82-92. | Zbl 0584.90063
[009] [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. | Zbl 0598.90066
[010] [11] G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Optimization, Wiley, New York, 1988. | Zbl 0652.90067
[011] [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.
[012] [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). | Zbl 0890.90147
[013] [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). | Zbl 0890.90147
[014] [15] G. Scheithauer and J. Terno, Equivalence of cutting stock problems, Working Paper, TU Dresden, 1993. | Zbl 0818.90083
[015] [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. | Zbl 0657.65089
[016] [17] G. Wäscher and T. Gau, Two approaches to the cutting stock problem, IFORS '93 Conference, Lisboa 1993. | Zbl 0918.90117