×

An improvement of Viswanathan and Bagchi’s exact algorithm for constrained two-dimensional cutting stock. (English) Zbl 0914.90225

Summary: K. V. Viswanathan and A. Bagchi [Oper. Res. 41, No. 4, 768-776 have proposed a bottom-up algorithm which combines in the nice tree-search procedure Gilmore and Gomory’s algorithm, called at each node of the tree, for solving exactly the constrained two-dimensional cutting problem. This algorithm is one of the best exact algorithms known today. In this paper, we propose an improved version of this algorithm by introducing one-dimensional bounded knapsacks in the original algorithm. Then, by exploiting dynamic programming properties, we obtain good lower and upper bounds which lead to significant branching cuts. Finally, the improved version is compared to the standard version of Viswanathan and Bagchi on some small and medium instances.

MSC:

90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Viswanathan, K. V.; Bagchi, A., Best-first search methods for constrained two-dimensional cutting stock problems, Operations Research, 41, 4, 768-776 (1993) · Zbl 0782.90076
[2] Beasley, J. E., Algorithms for unconstrained two-dimensional guillotine cutting, Journal of the Operational Research Society, 36, 297-306 (1985) · Zbl 0589.90040
[3] Dowsland, K.; Dowsland, W., Packing problems, European Journal of Operational Research, 56, 2-14 (1992) · Zbl 0825.90355
[4] Gilmore, P.; Gomory, R., Multistage cutting problems of two and more dimensions, Operations Research, 13, 94-119 (1965) · Zbl 0128.39601
[5] Kantorovich, L. V., Mathematical methods of organizing and planning production, Management Science, 6, 363-422 (1960) · Zbl 0995.90532
[6] Syslo, M.; Deo, N.; Kowalik, J., Discrete Optimization Algorithms (1983), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0574.90057
[7] Sweeney, P.; Paternoster, E., Cutting and packing problems: a categorized application-oriented research bibliography, Journal of the Operational Research Society, 43, 7, 691-706 (1992) · Zbl 0757.90055
[8] Gilmore, P.; Gomory, R., The theory and computation of knapsack functions, Operations Research, 14, 1045-1074 (1966) · Zbl 0173.21502
[9] Herz, J. C., A recursive computing procedure for two-dimensional stock cutting, IBM Journal of Research and Development, 16, 462-469 (1972) · Zbl 0265.90057
[10] Christofides, N.; Whitlock, C., An algorithm for two-dimensional cutting problems, Operations Research, 25, 31-44 (1977) · Zbl 0369.90059
[11] Wang, P. Y., Two algorithms for constrained two-dimensional cutting stock problems, Operations Research, 31, 3, 573-586 (1983) · Zbl 0517.90093
[12] Oliveira, J. F.; Ferreira, J. S., An improved version of Wang’s algorithm for two-dimensional cutting problems, European Journal of Operational Research, 44, 256-266 (1990) · Zbl 0684.90073
[13] Fayard, D.; Zissimopoulos, V., An approximation algorithm for solving unconstrained two-dimensional knapsack problems, European Journal of Operational Research, 84, 618-632 (1995) · Zbl 0928.90076
[14] Fayard, D.; Hifi, M.; Zissimopoulos, V., A general algorithm for two-dimensional cutting (1995), Ecomath, Université Paris: Ecomath, Université Paris Paris, Preprint · Zbl 1140.90374
[15] Zissimopoulos, V., Heuristic methods for solving (un)constrained two-dimensional cutting stock problems, Methods of Operations Research, 49, 345-357 (1984) · Zbl 0593.90039
[16] Morabito, R.; Arenales, M.; Arcaro, V., An and/or-graph approach for two-dimensional cutting problems, European Journal of Operational Research, 58, 2, 263-271 (1992) · Zbl 0757.90071
[17] Hifi, M., Study of some combinatorial optimization problems: cutting stock, rectangular packing and set covering problems, (Ph.D. thesis (1994), University of Paris 1: University of Paris 1 Panthéon-Sorbonne)
[18] Hifi, M., The DH/KD algorithm: a hybrid approach for unconstrained two-dimensional cutting problems, European Journal of Operational Research, 0, 0 (1997), (to appear) · Zbl 0929.90073
[19] Desler, J. F.; Hakimi, S. L., A graph theoretic approach to a class of integer programming problems, Operations Research, 17, 1017-1033 (1969) · Zbl 0183.49006
[20] Toth, P., Dynamic programming algorithms for zero-one knapsack problem, Computing, 25, 29-45 (1980) · Zbl 0431.90076
[21] Sakarovich, M., Optimisation Combinatoire, Programmation Discrète (1984), Hermann Editeurs des Sciences et des Arts
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.