This piece of software implements the L-approach for solving the 
manufacturer's pallet loading problem described in [1] and introduced in [2].

[1] E. G. Birgin, R. Morabito and F. H. Nishihara, A note on an L-approach
for solving the manufacturer's pallet loading problem, Journal of the 
Operational Research Society 56, pp. 1448-1451, 2005. 

[2] L. lins, S. Lins and R. Morabito, An L-approach for packing 
(l,w)-rectangles into rectangular and L-shaped pieces, Journal of the 
Operational Research Society 54, pp. 777-789, 2003.

This instructions guides you on how to install and run it in a SUN, Solaris 
or Linux platform (installation in a Windows platform is also possible,
but it may vary from system to system, depending on the compiler you have).

Description of the files:
=========================

lapproach.c util.c draw.c util.h and draw.h : implement the L-approach for
                                              solving the manufacturer's
                                              pallet loading problem

genmetapost.c                               : using a text output file generated
                                              by the main program, produces a
                                              metapost graphical representation
                                              of the solution

solution.tex                                : a latex file to generate a
                                              postscript file of the solution

Cover1b.dat Cover2b.dat Hard16probs.dat     : problems selected from Cover I
                                              and II sets, respectively, and
                                              the 16 hard instances. The 5
                                              columns in the files means L, W,
                                              l, w and n, respectively. L and W
                                              are the rectangular pallet 
                                              dimensions satisfying L >= W.
                                              l and w are the rectangular item
                                              dimensions satisfying l >= w. n
                                              is the reported number of packed
                                              items.

Cover1b.out Cover2b.out Hard16probs.out     : the output files for the problems
                                              in the files *.dat, generated by
                                              the L-approach implementation
                                              described here. The last column
                                              corresponds to the CPU runtime
                                              in a 1533 Mhz AMD Athlon (TM)
                                              MP 1800+ processor.

How to compile:
===============

Type

gcc -O4 lapproach.c util.c draw.c -o lapproach

to compile the main program and

gcc -O4 genmetapost.c -o genmetapost

to compile the program which converts the text output file into a metapost
graphical representation of the solution.

How to run:
===========

Just type

lapproach

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 item to be packed, also satisfying l >= w.

In the current implementation, L, W, l and w must be less than or equal 
to 1024.

After having entered the data of the problem, if your computer has enough
memory to solve the desired problem, the program will answer the number of
packed rectangles. It will also generate a text file called solution.txt
with information needed to generate a graphical representation of the solution.

How to generate the graphical representation of the solution:
=============================================================

First you need to generate the metapost file representing the solution. To do
this, just type

genmetapost

It will generate a file called solution.mp.

Second, you need to compile this metapost file typing

mpost solution.mp

It will generate a file called solution.1

Finally, to generate the postcript file, just type

latex solution.tex

and then

dvips solution.dvi -o solution.ps

The postscript representation of the solution will be in the file called
solution.ps.

To see this file, type, for example,

gv solution.ps