This software implements a procedure called NEWPACK for solving 
the problem of finding the smallest circular object in which a set
of identical circular items can be packed. This work is described in:

E. G. Birgin and J. M. Gentil,
"New and improved results for packing identical unitary radius circles
within triangles, rectangles and strips", submitted, 2009.

The program uses ALGENCAN, a nonlinear programming algorithm based on
Augmented Lagrangians, to solve the nonlinear model. Its latest
version is available at TANGO website:

http://www.ime.usp.br/~egbirgin/tango


This instructions guide you on how to install and run it in Linux
platform (installation in other platform is also possible, but it may
vary from system to system, depending on the compiler you have).


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

newpack-cc-mina.f       : implements the procedure which solves the
                          problem of finding the smallest circular
                          object in which a fixed set of identical
                          circular items can be packed.

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

In files/

cc-mina-1.dat,...,
   cc-mina-100.dat      : files with solution data for each instance of
                          the problem we solved. The radii of the
	                  circular items considered here was 1.

cc-mina-1.mp,...,
   cc-mina-100.mp       : Metapost files with the graphical representation
                          of the solutions found. The radii of the circular
                          items considered here was 1.



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

Type

  f77 -xf77-cpp-input -O4 newpack-cc-mina.f -o newpack-cc-mina



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

Type

  newpack-cc-mina

The program will ask information about the radius of the circular
items, number of items to be packed and the maximum CPU time the
method will use.

Solution will be saved in the output file solution.dat. Moreover,
everything that appears in the screen will be also saved in the file
algencan.out. The the graphical representation of the best solution
found is saved in the Metapost file solution.mp.

OBS: In order to have better results, we recommend you to create a file
'algencan.dat' with the following lines:

FEASIBILITY-TOLERANCE 1.0D-5
HESSIANS-PROVIDED
UNPRECONDITIONED-CG

These options are used by ALGENCAN
You can see (and change) all the options ALGENCAN can use in the file
'newpack-cc-mina.f'.



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

- Compile the metapost file generated by NEWPACK typing

mpost solution.mp

- It will generate a file called solution.1
  Rename it to figure.1:

mv solution.1 figure.1

- Then, to generate the postcript file, just type

latex figures.tex

  and then

dvips figures.dvi -o figures.ps

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

  To see this file, type, for example,

gv figures.ps