zbMATH — the first resource for mathematics

An exact algorithm for general, orthogonal, two-dimensional knapsack problems. (English) Zbl 0903.90124
Summary: We present a new exact tree-search procedure for solving two-dimensional knapsack problems in which a number of small rectangular pieces, each of a given size and value, are required to be cut from a large rectangular stock plate. The objective is to maximize the value of pieces cut or minimize the wastage. We consider the case where there is a maximum number of times that a piece may be used in a cutting pattern. The algorithm limits the size of the tree search by using a bound derived from a Lagrangean relaxation of a 0-1 integer programming formulation of the problem. Subgradient optimization is used to optimize this bound. Reduction tests derived from both the original problem and the Lagrangean relaxation produce substantial computational gains. The computational performance of the algorithm indicates that it is an effective procedure capable of solving optimally practical two-dimensional cutting problems of medium size.

90C10 Integer programming
Full Text: DOI
[1] Baker, B.; Brown, D.; Katseff, H., A 5/4 algorithm for two-dimensional packing, Journal of algorithms, 2, 348-368, (1981) · Zbl 0472.68032
[2] Baker, B.; Coffman, E.; Rivest, R., Orthogonal packing in two dimensions, SIAM journal on computing, 9, 846-855, (1980) · Zbl 0447.68080
[3] Beasley, J.E., Algorithms for unconstrained two-dimensional guillotine cutting, Journal of the operational research society, 36, 297-306, (1985) · Zbl 0589.90040
[4] Beasley, J.E., An exact two-dimensional non-guillotine cutting tree-search procedure, Operations research, 33, 49-64, (1985) · Zbl 0569.90038
[5] Biro, M.; Boros, E., Network flows and non-guillotine cutting patterns, European journal of operational research, 16, 215-221, (1984) · Zbl 0542.05054
[6] Bischoff, E.; Dowsland, E.B., An application of the micro to product design and distribution, Journal of the operational research society, 33, 271-280, (1982)
[7] Christofides, N.; Hadjiconstantinou, E., An exact algorithm for orthogonal 2-D cutting problems using guillotine cuts, European journal of operational research, 83, 21-38, (1992) · Zbl 0903.90134
[8] Christofides, N.; Whitlock, C.A., An algorithm for two-dimensional cutting problems, Operations research, 25, 30-44, (1977) · Zbl 0369.90059
[9] Coffman, E.G.; Shor, P.W., Average-case analysis of cutting and packing in two dimensions, European journal of operational research, 44, 134-144, (1990) · Zbl 0689.90059
[10] Coffman, E.G.; Garey, M.R.; Johnson, D.S., Approximation algorithms for bin-packing - an updated survey, (), 49-106, Wien · Zbl 0558.68062
[11] Dagli, C.H.; Tatoglu, M.Y., An approach to two-dimensional cutting stock problems, International journal of production research, 25, 175-190, (1987) · Zbl 0612.90066
[12] Daniels, J.J.; Ghandforoush, P., An improved algorithm for the non-guillotine constrained cutting-stock problem, Journal of the operational research society, 41, 141-149, (1990) · Zbl 0693.90043
[13] Dowsland, K.A., An exact algorithm for the pallet-loading problem, European journal of operational research, 31, 78-84, (1987) · Zbl 0614.90084
[14] Dowsland, K.A., Efficient automated pallet loading, European journal of operational research, 44, 232-238, (1990) · Zbl 0684.90078
[15] Dyckhoff, H., A typology of cutting and packing problems, European journal of operational research, 44, 145-159, (1990) · Zbl 0684.90076
[16] Dyckhoff, H.; Finke, ()
[17] Dyckhoff, H., Classification of real world trim loss problems, (), 191-208
[18] Farley, A.A., The cutting stock problem in the canvas industry, European journal of operational research, 44, 247-255, (1990) · Zbl 0684.90080
[19] Fisher, M.L., The Lagrangean relaxation method for solving integer programming problems, Management science, 27, 1-18, (1981) · Zbl 0466.90054
[20] Gilmore, P.C.; Gomory, R.E., Multistage cutting stock problems of two and more dimensions, Operations research, 13, 94-120, (1965) · Zbl 0128.39601
[21] Gilmore, P.C.; Gomory, R.E., The theory and computation of knapsack functions, Operations research, 15, 1045-1074, (1967) · Zbl 0173.21502
[22] Golden, B., Approaches to the cutting stock problem, American institute of industrial engineers transactions, 8, 205-274, (1976)
[23] Haessler, R.W.; Sweeney, P.E., Cutting stock problem and solution procedures, European journal of operational research, 54, 141-150, (1991) · Zbl 0736.90062
[24] Held, M.; Karp, M., The travelling salesman problem and minimum spanning trees, part II, Mathematiaal programming, 1, 6-25, (1971) · Zbl 0232.90038
[25] Held, M.; Wolfe, P.; Crowder, H.P., Validation of subgradient optimization, Mathematical programming, 6, 62-88, (1974) · Zbl 0284.90057
[26] Herz, J., Recursive computational procedure for two-dimensional stock cutting, IBM journal of research and development, 16, 462-469, (1972) · Zbl 0265.90057
[27] Hinxman, A.I., The trim loss and assortment problems: A survey, European journal of operational research, 5, 8-18, (1980) · Zbl 0442.90072
[28] Hodgson, T., A combined approach to the pallet loading problem, IIE transaction, 14, 175-182, (1982)
[29] Hodgson, T.; Hughes, D.; Martin-Vega, L., A note on a combined approach to the pallet loading problem, IIE transactions, 15, 268-271, (1983)
[30] Madsen, O.B.G., References concerning the cutting stock problem, (1980), IMSOR, The Technical University of Denmark DK-2800, Lyngby, Denmark · Zbl 0441.90028
[31] Martello, S.; Toth, P., Knapsack problems - algorithms and computer implementations, (1990), Wiley Chichester UK · Zbl 0708.68002
[32] Oliveira, J.F.; Ferreira, J.S., An improved version of Wang’s algorithm for two-dimensional cutting stock problems, European journal of operational research, 44, 256-266, (1990) · Zbl 0684.90073
[33] Sahni, S.; Horowitz, E., Fundamentals of computer algorithms, (1979), Pitman London
[34] Smith, A.; De Cani, P., An algorithm to optimise the pattern of boxes in pallets, Journal of the operational research society, 31, 573-578, (1980)
[35] Wang, P.Y., Two algorithms for constrained two-dimensional cutting stock problems, Operations research, 31, 73-586, (1983) · Zbl 0517.90093
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.