This piece of software implements the procedure called GENPACK for 
solving the problem of packing identical orthogonal rectangles into an 
arbitrary convex region, described in [1] and [2].

[1] E. G. Birgin, J. M. Martínez, F. H. Nishihara and D. P. Ronconi,
Orthogonal packing of rectangular items within arbitrary convex regions 
by nonlinear optimization, Computers & Operations Research 33, 
pp. 3535-3548, 2006.

[2] E. G. Birgin and J. M. Martínez, Large-scale active-set box-constrained 
optimization method with spectral projected gradients, Computational 
Optimization and Applications 23, pp. 101-125, 2002.

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:
=========================

genpack.f           : implements the procedure called GENPACK for solving  
                      the problem of packing identical orthogonal rectangles 
                      into an arbitrary convex region.

solution.tex        : is a latex file that you can use to generate a 
                      postscript file with the graphical representation of 
                      the solution.

genpack.out         : is a text file with the output generated by GENPACK 
                      when used to solve the 21 problems presented in [1].

p01.mp, ..., p21.mp : are the 21 MetaPost files, automaticaly generated by
                      GENPACK, which contain the graphical representation
                      of the solutions.

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

Type

f77 -O4 genpack.f -o genpack

(If the compiler gives you a "warning" just ignore it.)

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

Just type

genpack

The program will ask you which problem you would like to solve 
(choose a number between 1 and 21 to solve one of the 21 problems
presented in [1]) and the maximum CPU time the method will used.

The program will show in the screen the number of rectangles it is
being packing until the upper bound is reached or the time is exhausted.

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

Compile the metapost file generated by GENPACK typing

mpost solution.mp

It will generate a file called solution.1

Then, to generate the postcript file, just type

latex solution.tex

and then

dvips solution.dvi -o solution.ps

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

To see this file, type, for example,

gv solution.ps

How to solve your own problem:
==============================

To solve your own problem you just need a rudimentary acknowledge of
Fortran 77 programming language to edit the main file genpack.f.

In this file you will need add the information of your problem in
the following subroutines:

DEFPRO is the subroutine which defines some information of the problem.
------

Rectangular item information:
-----------------------------

dx = half of the horizontal side of the rectangles
dy = half of the vertical side of the rectangles

Box constraints of the convex region:
-------------------------------------

lx = lower bound for the x-axis 
ux = upper bound for the x-axis 
ly = lower bound for the y-axis 
uy = upper bound for the y-axis 

Extra-information of the convex region:
---------------------------------------

This four parameters must represent a limited box that contains the
convex region. See, for example, problems 4, 5, 6 and 11 that have 
their boxes (which ARE NOT part of the definition of the convex region) 
drawed in [1]. You can see that these boxes do not take part in the
definition of the convex regions at Table 1 of [1].

xmin = containing-box lower bound for the x-axis 
xmax = containing-box upper bound for the y-axis
ymin = containing-box lower bound for the x-axis
ymax = containing-box upper bound for the y-axis

More information of the convex region:
--------------------------------------

r = number of smooth functions in the definition of the convex region

EVALW   is the subroutine that implements the smooth functions that define
-----   the convex region.

EVALDW  is the subroutine that computes the derivatives of the smooth
------  functions that define the convex region.

DRAWSOL is the subroutine that draws the graphical representation of the
------- solution. The piece of code that draws the packed items is common 
        to all the problems and you do not need to modify it. You just 
        need to add the piece of code that draws the convex region. If you 
        are not interested in the graphical representation of the solution, 
        you may skip this subroutine.

After having modified the four subroutines, just compile the program and
run it as explained above.