Abstract
Many cutting problems on two- or three-dimensional objects require that the cuts be orthogonal and of guillotine type. However, there are applications in which the cuts must be orthogonal but need not be of guillotine type. In this paper we focus on the latter type of cuts on rectangular bins. We investigate the so-called \(L\)-approach, introduced by Lins et al. (J Oper Res Soc 54:777–789, 2003), which has been used to tackle, among others, the pallet loading problem and the two-dimensional unconstrained knapsack problem. This approach concerns a method to generate two \(L\)-shaped pieces from an \(L\)-shaped piece. More recently, Birgin et al. (J Oper Res Soc 63(2):183–200, 2012), raised two questions concerning this approach. The first question is whether one may restrict only to cuts on raster points (rather than on all discretization points), without loss in the quality of the solution. We prove that the answer to this question is positive. The second question is whether the \(L\)-approach is an optimal method to solve the unconstrained knapsack problem. We show an instance of the problem for which this approach fails to find an optimum solution.
Similar content being viewed by others
References
Alvarez-Valdes R, Parreño F, Tamarit JM (2005) A branch-and-cut algorithm for the pallet loading problem. Comput Oper Res 32(11):3007–3029
Baldacci RB, Boschetti MA (2007) A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem. Eur J Oper Res 183:1136–1149
Beasley JE (1985) An exact two-dimensional non-guillotine cutting tree search procedure. Oper Res 33(1):49–64
Beasley JE (1990) OR-Library: distributing test problems by electronic mail. J Oper Res Soc 41(11):1069–1072
Birgin EG, Lobato RD, Morabito R (2010) An effective recursive partitioning approach for the packing of identical rectangles in a rectangle. J Oper Res Soc 61(2):306–320
Birgin EG, Lobato RD, Morabito R (2012) Generating unconstrained two-dimensional non-guillotine cutting patterns by a recursive partitioning algorithm. J Oper Res Soc 63(2):183–200
Caprara A, Monaci M (2004) On the two-dimensional knapsack problem. Oper Res Lett 32:5–14
Caprara A, Lodi A, Monaci M (2010) An approximation scheme for the two-stage, two-dimensional knapsack problem. Discret Optim 7(3):114–124
Cintra GF, Miyazawa FK, Wakabayashi Y, Xavier EC (2008) Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation. Eur J Oper Res 191:59–83
Del Valle AM, Queiroz TA, Miyazawa FK, Xavier EC (2012) Heuristics for two-dimensional knapsack and cutting stock problems with items of irregular shape. Expert Syst Appl 39(16):12589–12598
Dolatabadi M, Lodi A, Monaci M (2012) Exact algorithms for the two-dimensional guillotine knapsack. Comput Oper Res 39:48–53
Fayard D, Zissimopoulos V (1995) An approximation algorithm for solving unconstrained two-dimensional knapsack problems. Eur J Oper Res 84:618–632
Fekete SP, Schepers J, van der Veen J (2007) An exact algorithm for higher-dimensional orthogonal packing. Oper Res 55(3):569–587
Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco
Herz JC (1972) A recursive computational procedure for two-dimensional stock-cutting. IBM J Res Dev 16(5):462–469
Kulik A, Shachnai H (2010) There is no EPTAS for two-dimensional knapsack. Inf Process Lett 110(16):707–710
Lins L, Lins S, Morabito R (2003) An L-approach for packing \((l, w)\)-rectangles into rectangular and L-shaped pieces. J Oper Res Soc 54:777–789
Pureza V, Morabito R (2006) Some experiments with a simple tabu search algorithm for the manufacturer’s pallet loading problem. Comput Oper Res 33(3):804–819
Queiroz TA, Miyazawa F, Wakabayashi Y, Xavier E (2012) Algorithms for 3D guillotine cutting problems: unbounded knapsack, cutting stock and strip packing. Comput Oper Res 39:200–212
Russo M, Sforzab A, Sterle C (2013) An improvement of the knapsack function based algorithm of Gilmore and Gomory for the unconstrained two-dimensional guillotine cutting problem. Int J Prod Econ 145(2):451–462
Scheithauer G, Terno J (1996) The G4-heuristic for the pallet loading problem. J Oper Res Soc 47:511–522
Acknowledgments
The authors would like to thank the referees for the suggestions and comments that helped improving the presentation of this paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Research partially supported by CAPES, CNPq (Proc. 471351/2012-1, 477203/2012-4, 477692/2012-5, 306860/2010-4, 303987/2010-3), FAPEG, FAPESP (Proc. 2013/03447-6, 2013/08278-8) and Project MaCLinC at USP.
Rights and permissions
About this article
Cite this article
de Queiroz, T.A., Miyazawa, F.K. & Wakabayashi, Y. On the \(L\)-approach for generating unconstrained two-dimensional non-guillotine cutting patterns. 4OR-Q J Oper Res 13, 199–219 (2015). https://doi.org/10.1007/s10288-014-0274-3
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10288-014-0274-3
Keywords
- Combinatorial problems
- Cutting
- Two-dimensional unconstrained knapsack problem
- Non-guillotine cut
- \(L\)-pattern
- Raster point