PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
1995-1996 | 23 | 2 | 151-167
Tytuł artykułu

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

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Rocznik
Tom
23
Numer
2
Strony
151-167
Opis fizyczny
Daty
wydano
1995
otrzymano
1994-05-05
Twórcy
  • Institute of Numerical Mathematics, Technical University Dresden, Mommsenstr. 13, D-01062 Dresden, Germany
  • Institute of Numerical Mathematics, Technical University Dresden, Mommsenstr. 13, D-01062 Dresden, Germany
Bibliografia
  • [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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-zmv23i2p151bwm
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.