This page is dedicated to the article [1]. You can find the data sets and the numerical results presented in [1], as well as the computer implementation of the algorithm in C/C++. You can also run the algorithm through our Web interface. IntroductionThe problem consists in arranging, without overlapping, identical rectangular pieces (boxes) with length l and width w in a rectangular pallet with length L and width W. The boxes must be placed orthogonally (i.e., with each side of the boxes orthogonal to one side of the pallet) and only 90degree rotations are allowed. The objective is to find a pattern with the maximum number of boxes packed. This twodimensional packing problem is also known as the manufacturer's pallet loading problem. We assume that L, W, l and w are integers and L ≥ W and l ≥ w without loss of generality. Thus, a problem is determined by the quadruple (L,W,l,w). This packing problem can be classified as 2/B/O/C according to Dyckhoff's typology of cutting and packing problems, and as "twodimensional, rectangular Identical Item Packing Problem (IIPP)" based on Wäscher, Haußner and Schumann's typology. Recursive Fiveblock AlgorithmThe Recursive Fiveblock Algorithm [1] is a modified implementation of the algorithm described in [4]. Basically, the algorithm divides the rectangle into, at most, five regions through firstorder nonguillotine cuts, as showed below. Then, the algorithm is called recursively for each region produced. You can run this algorithm online.
LAlgorithmLAlgorithm has been proposed and described in [2] and [3]. This algorithm is more general than the Recursive Fiveblock Algorithm. Besides producing firstorder nonguillotine patterns, it also produces other ones that appear when the rectangle is divided in Lshaped regions. The figures below show an example of a pattern obtained by Lshaped cuts and the solution found by LAlgorithm for the problem (L,W,l,w) = (49,28,8,3). In [1] we describe two new ways of dividing an Lshaped piece into two Lshaped pieces, which were not considered in [3]. Run the LAlgorithm!
Recursive Partitioning Algorithm  A combined algorithmThis algorithm (described in [1]) combines the speed of the Recursive Fiveblock Algorithm and the robustness of the LAlgorithm. First, it tries to solve the problem with the Recursive Fiveblock Algorithm. If the solution found is not optimal (or, at least, if it is not possible to prove its optimality), the LAlgorithm is called to solve the problem. Moreover, all information obtained by the first algorithm is used by the second one. Run it through our Web interface.Download: RecursivePartitioningAlgorithm.tar.gz How to compile and run
To compile, just type g++ O3 RecPartAlgorithm.cpp bd.cpp draw.cpp draw_bd.cpp graphics.cpp \ sets.cpp util.cpp o RecPartAlgorithm
The executable file created will be called
The program will ask you L and W, the dimensions of the
rectangular pallet satisfying L ≥ W. Then, it will ask
you l and w, the dimensions of the rectangular items to be
packed, also satisfying l ≥ w.
After having entered the data of the problem, the program will answer
the number of packed rectangles. It will also generate a MetaPost
file called For example, to run the Recursive Partitioning Algorithm to solve the problem (L,W,l,w) = (49,28,8,3), you must type: ./RecPartAlgorithm L and W: 49 28 l and w: 8 3 The output will be similar to this: Phase 1 (Fiveblock Algorithm)  solution found: 56 boxes.  runtime: 0.00 second. Phase 2 (LAlgorithm)  solution found: 57 boxes.  runtime: 0.26 second. Solution found: 57 boxes. Computed upper bound: 57 boxes. Proven optimal solution. Runtime: 0.26 second. Visualizing the solutionThe program creates two files, namely,solution.mp and
solution.svg , that graphically represent the solution in
MetaPost
and SVG formats,
respectively. There are two options for visualizing the solution
found. The first one is by simply using some SVG viewer to
view the file solution.svg . For the second option, you
need MetaPost
and a Latex implementation
installed on your system. Then compile the file
solution.tex in the same directory of
solution.mp .
mpost solution.mp latex solution.texIt creates a file called solution.dvi which can be
visualized with a DVI
viewer. If you wish, you can convert this file into a PDF file:
dvipdf solution.dvi Data setsBelow you can get the data sets used in the experiments described in [1].
The updated Cover IIIB, as described in [1], is available. The last update was made on January 11th, 2009. The detailed progress can also be viewed. Numerical resultsThe experiments were run on a 2.4GHz Intel® Core™2 Quad Q6600 with 4.0GB of RAM memory and Linux Operating System. Below you can get our output files.
Contact
SponsorsThis work was partially supported by the Brazilian agencies FAPESP (Fundação de Amparo à Pesquisa do Estado de São Paulo) and CNPq (Conselho Nacional de Pesquisa e Desenvolvimento). References
