This Web site provides additional material to the paper

E. G. Birgin and R. D. Lobato. Orthogonal packing of identical rectangles within isotropic convex regions. Computers & Industrial Engineering (2010) 59, 595–602.

The full text is locally available in PDF and PS formats. The full text can also be found at ScienceDirect. The computer implementation in Fortran 77/95 is available to download under the terms of the GNU General Public License. Below you can find instructions on how to compile and run the program, visualize the solution, and modify the program in order to solve your own instance of the problem. If you have any question, please send an e-mail to .

Compiling and running it

To compile the program, just type
./compile.sh
To run it, type
./igenpack
Problem number 4 with 28
rectangles packed. The program will ask you which problem you would like to solve (choose a number between 1 and 16 to solve one of the 16 problems presented in the paper) and the minimum and maximum number of rectangles the method will try to pack. The program will output the number of rectangles that have been packed until the upper bound is reached.

Graphical representation of the solution

To generate the graphical representation of the solution, first compile the MetaPost file solution.mp, which was created by IAlgencan, by typing
mpost solution.mp
It will generate a file called solution.1. Then, to create a PostScript 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

Solving your own problem

To solve your own instance of the problem, you just need a basic knowledge of Fortran 77/95 programming language to edit the file Packing.f95. In this file you will need add the information of your problem in the following subroutines:
  • DEFPRO is the subroutine that 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

    The following 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) drawn in Figure 2 of the paper. You can see that these boxes do not take part in the definition of the convex regions in Table 1 of the paper.

    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.

Sponsor

This work was partially supported by the Brazilian agency FAPESP (Fundação de Amparo à Pesquisa do Estado de São Paulo).


DCC - IME - USP

Valid XHTML 1.0 Strict

Valid CSS!