A Comparative Study of Exact Algorithms for the Two Dimensional Strip Packing Problem

Document Type: Research Paper

Authors

ICD-LOSI, (CNRS FRE 2848) UNIVERSITE DE TECHNOLOGIE DE TROYES FRANCE

Abstract

In this paper we consider a two dimensional strip packing problem. The problem consists of packing a set of rectangular items in one strip of width W and infinite height. They must be packed without overlapping, parallel to the edge of the strip and we assume that the items are oriented, i.e. they cannot be rotated. To solve this problem, we use three exact methods: a branch and bound method, a dichotomous algorithm and a branch and price method. The three methods were carried out and compared on literature instances.

Keywords


[1] Barnhart C., Johnson E. L., Nemhauser G. L., Savelsbergh M. W. P., Vance P. H. (1998), Branch-andprice:
column generation for solving huge integer programs, Operations Research, 46; 316-329
[2] Beasley J. E. (1985), An exact two-dimensional non-guillotine cutting tree search procedure,
Operations Research 33; 49-64.
[3] Bekrar A., Kacem I., Chu C., Sadfi C. (2006a), Des Stratégies d'amélioration de l'heuristique SHF pour
le problème de découpe guillotine en deux dimensions, Proceedings of ROADEF'06 Conference, Lille,
France (available on CD).
[4] Bekrar A., Kacem I., Chu C., Sadfi C. (2006b), A Branch and Bound Algorithm for solving the 2D
Strip Packing Problem, Proceedings of IC SSSM'06, IEEE Conference, Troyes (France), 940-946.
[5] Beltran J. D., Calderon J. E., Cabrera R. J., Moreno Perez J. A., Moreno-Vega J. M. (2004),
GRASP/VNS hybrid for the strip packing Problem, Proceedings of the First International Workshop on
Hybrid Metaheuristics (HM 2004), Valencia, Spain, 22-23.
[6] Ben Messaoud S., Chu C., Espinouse M.L. (2003), SHF : Une nouvelle heuristique pour le
problème de découpe guillotine en 2D, Proceedings of MOSIM'03, Toulouse (France).
[7] Berkey J. O., Wang P. Y. (1987), Two dimensional finite bin packing algorithms, J. of Oper. Res. Soc.
38; 423-429.
[8] Bortfeldt A. (2006), A genetic algorithm for the two-dimensional strip packing problem with
rectangular pieces, European Journal of Operational Research 172(3); 814-837.
[9] Boschetti M., Hadjiconstantinou E., Mingozzi A. (2002), New upper bounds for the two-dimensional
orthogonal non guillotine cutting stock problem, IMA Journal of Management Mathematics 13; 95-
119.
[10] Boschetti M. A., Mingozzi A. (2003), The two-dimensional finite bin packing problem. Part I: New
lower bounds for the oriented case, 4OR: Quarterly Journal of the Belgian, French and Italian
Operations Research Societies, Volume 1, N° 1, 27 -42.
[11] Caprara A., Monaci M. (2004), On the 2-Dimensional Knapsack Problem, Operations Research
Letters 32; pp. 5-14.
[12] Chung F.K.R., Garey M.R., Johnson D.S. (1982), On packing two-dimmensional bins, SIAM Journal
of Algebraic and Discrete Methods 3 ; 66-76.
[13] Cintra G. F., Miyazawa F. K., Wakabayashi Y., Xavier E. C. (2006), Algorithms for two-dimensional
cutting stock and strip packing problems using dynamic programming and column generation,
European Journal of Operational Research, accepted for publication.
[14] Clautiaux F., Carlier J., Moukrim A. (2006a), A new exact method for the two-dimensional binpacking
problem with fixed orientation, Oper. Res. Lett., doi: 10.1016/j.orl.2006.06.007.
[15] Clautiaux F., Jouglet A., Carlier J., Moukrim A. (2006b), A new constraint programming approach
for the orthogonal packing problem, Computers and Operations Research,
doi:10.1016/j.cor.2006.05.012.
[16] Cui Y., Yang Y., Cheng X., Song P. (2006), A recursive branch-and-bound algorithm for the
rectangular guillotine strip packing problem, Computers and Operations Research, doi:
10.1016/j.cor.2006.08.011.
[17] Fekete S. P., Schepers J. (1997), A new exact algorithm for general orthogonal d-dimensional
knapsack problems, technical report, Mathematisches Institut, Universität zu Köln.
[18] Fekete S., Schepers J. (2001), New Classes of Fast Lower Bounds for Bin Packing Problems,
Mathematical Programming 91; 11-31
[19] Fekete S.P., Schepers J., van der Veen J. (2007), An exact algorithm for higher-dimensional
orthogonal packing, To appear in Operations Research.
[20] Fernandez de la Vega W., Zissimopoulos Damath, V. (1998), An Approximation scheme For Strip-
Packing of Rectangles With Bounded Dimensions, Discrete Applied Mathematics and Combinatorial
Operations Research and Computer Science 82; 93-101.
[21] Garey M. R., Johnson D. S. (1978), Computers and intractability, a guide to the theory of NPcompleteness;
Freeman, New York.
[22] Gomes Miguel A., Oliveira Jose F. (2006), Solving Irregular Strip Packing Problems by Hyberdising
Simulated Annealing and Linear Programming, European Journal of Operations Research 171(3);
811-829.
[23] Hadjiconstantinou E., Christofides N. (1995), An Exact Algorithm for General, Orthogonal, Two-
Dimensional Knapsack Problem, European Journal of Operational Research 83; 39-56.
[24] Hifi M. (1998), Exact algorithms for the guillotine strip cutting/packing problem, Computers &
Operations Research 25(11); 925-940.
[25] Hopper E. Turton B. C. H. (2001), A Review of the Application of Meta-Heuristic Algorithms to 2D
Strip Packing, Artificial Intelligence Review 16; 257 -300.
[26] Kenyon C., Remila E. (1996), Approximate Strip-Packing, Proceedings of the 37th Annual
Symposium on Foundations of Computer Science (FOCS'96), Burlington, 31-37.
[27] Lesh N., Marks J., McMahon A., Mitzenmacher. M. (2003), New Heuristic and Interactive
Approaches to 2D Rectangular Strip Packing, Report N° TR2003-18 July 2003, Mitsubishi Electric
Research Laboratories, http://www.merl.com.
[28] Martello S., Monaci M., Vigo D. (2003), An Exact Approach to the Strip Packing Problem,
INFORMS Journal on Computing 15(3); 310-319.
[29] Martello S., Pisinger D., Vigo D. (2000), The Three-Dimensional Bin Packing Problem, Operations
Research, 48(2); 256 – 267.
[30] Martello S., Toth P. (1990), Lower bounds and reduction procedures for the bin-packing problem,
Discrete Applied Mathematics 26; 59-70.
[31] Pisinger D., Sigurd M. (2005), The two-dimensional bin packing problem with variable bin sizes and
costs, Discrete Optimization 2(2); 154-167.
[32] Pisinger D., Sigurd M. (2007), Using Decomposition Techniques and Constraint Programming for
Solving the Two-Dimensional Bin-Packing Problem, INFORMS Journal on Computing 19(1); 36-51.
[33] Puchinger J., Raidl G. R. (2004), An evolutionary algorithm for column generation in integer
programming: an effective approach for 2D bin packing. In X. Yao et. al, editor, Parallel Problem
Solving from Nature -PPSN VIII, volume 3242 of LNCS; 642-651.
[34] Ryan D.M., Foster R.A. (1981), An integer programming approach to scheduling, In: A. Wren, Editor,
Computer Scheduling of Public Transport Urban Passenger Vehicle and Crew Scheduling; North-
Holland, Amsterdam, 269–280.
[35] Scheithauer G. (1998) Equivalence and Dominance for Problems of Optimal Packing of Rectangles,
Ricerca Operativa 27(83); 3-34.
[36] Vanderbeck F. (1999), Computational study of a column generation algorithm for bin packing and
cutting stock problems, Mathematical Programming 86(3); DOI 10.1007/s101070050105, 565-594.
[37] Zhang D., Kang Y., Deng A. (2006), A new heuristic recursive algorithm for the strip rectangular
packing Problem, Computers and Operations Research 33(8); 2209-2217.