How to compile

The Fortran version of EA06, FD05, and KB05 from the HSL Mathematical Software Library are required for compiling the software. To download EA06, FD05, and KB05, go to http://www.hsl.rl.ac.uk/. After decompressing the files you downloaded from HSL, you will find the files ea06d.f, ddeps.f, fd05d.f, and kb05i.f under the src directories. For example, these files could be found at:

ea06-1.0.0/src/ea06d.f
ea06-1.0.0/src/ddeps.f
fd05-1.0.0/src/fd05d.f
kb05-1.0.0/src/kb05i.f

Next, you must decompress the file packing-ellipsoids-2.tar.gz that you have downloaded from this website:

tar -zxvf packing-ellipsoids-2.tar.gz

It will create a directory called packing-ellipsoids-2. Enter this directory by typing:

cd packing-ellipsoids-2

There you can find a directory called third-party/hsl. You must put the files ea06d.f, ddeps.f, fd05d.f, and kb05i.f in that directory.

In the packing-ellipsoids-2 directory, you can find a file called dimension.txt. You must edit this file in order to define the dimension of the problem. If you want to pack two-dimensional ellipsoids, this file must contain the number 2. If you want to pack three-dimensional ellipsoids, this file must contain the number 3. Then, from the packing-ellipsoids-2 directory, type make to compile the code:

make

After the compilation, an executable file called packEllipsoids2D or packEllipsoids3D will be created in the current directory.

Defining your own problem

In order to solve your own problem, you must set a few options. These options must be set in a file of your choice. For example, you could put the options in a file called packing.opt.

Ellipsoids

The first option you should set is called NUMBER_OF_ELLIPSOIDS. This option defines the number of ellipsoids to be packed and must be followed by an integer number. Therefore, if you want to pack 100 ellipsoids, you should add the following line in the options file:

NUMBER_OF_ELLIPSOIDS 100

Next, you should define the dimensions of the ellipsoids to be packed. If the ellipsoids you want to pack are all identical, then you can use the IDENTICAL_ELLIPSOIDS option. This option must be followed by either two numbers (in case you want to pack two-dimensional ellipsoids) or three numbers (if you want to pack three-dimensional ellipsoids), which are the lengths of the semi-axes of the ellipsoids. For example, if you want to pack two-dimensional ellipsoids with semi-axis lengths 1.2 and 0.75, you should append the following line to the options file:

IDENTICAL_ELLIPSOIDS 1.2 0.75

If you want to pack three-dimensional ellipsoids with semi-axis lengths 5, 3 and 2.7, you should append the following line to the options file:

IDENTICAL_ELLIPSOIDS 5 3 2.7

If the ellipsoids you want to pack are non-identical, you can provide a file describing the semi-axis lengths of each ellipsoid. To specify the file that contains the lengths of the semi-axes of the ellipsoids, use the ELLIPSOID_DIMENSIONS_FILE_NAME option. For example, if the file containing this information is called ellipsoids.txt, then you should add the following line to the options file:

ELLIPSOID_DIMENSIONS_FILE_NAME ellipsoids.txt

In the two-dimensional case, this file must have the following format:

m
a1 b1
a2 b2
...
am bm

In the three-dimensional case, this file must have the following format:

m
a1 b1 c1
a2 b2 c2
...
am bm cm

The first line must contain an integer number m which is the number of ellipsoids. Then, each one of the next m lines must contain the lengths of the semi-axes (a and b in the two-dimensional case and a, b, and c in the three-dimensional case) of an ellipsoid. For example, if you want to pack 3 three-dimensional ellipsoids where the first one has semi-axis lengths 4.1, 3.2 and 1.1, the second one has semi-axis lengths 2.3, 2.3 and 2.1, and the third one has semi-axis lengths 5.6, 3.3 and 3.3, your file would have the following content:

3
4.1 3.2 1.1
2.3 2.3 2.1
5.6 3.3 3.3

Container

You can also specify the type of container where the ellipsoids will be packed in. All containers are centered at the origin.

Two-dimensional container

In the two-dimensional case, the container can be a circle, a square, a rectangle, or an ellipse. All containers are centered at the origin. The rectangular containers have their sides parallel to the coordinate axes. The elliptical container has its semi-axes parallel to the coordinate axes.

To select the container, you must use the appropriate option in the options file. To pack the ellipses within a circle, you should use the CIRCLE_CONTAINER option. To pack the ellipses within a square, use the SQUARE_CONTAINER option. To pack the ellipses within a rectangle, use the RECTANGLE_CONTAINER option. Finally, to pack the ellipses within an ellipse, use the ELLIPSE_CONTAINER option. These options do not require any further information.

If you want to pack the ellipses inside a minimizing area container, you must use the MINIMIZE_AREA option. This option does not require any further information.

Three-dimensional container

In the three-dimensional case, the container can be a ball, a cube, or a rectangular cuboid. All containers are centered at the origin. The cubic and cuboidal containers have their sides parallel to the coordinate axes.

To select the container, you must add the appropriate option to the options file. To pack the ellipsoids within a ball, you must use the BALL_CONTAINER option. To pack the ellipsoids within a cube, you must use the CUBE_CONTAINER option. Finally, to pack the ellipsoids within a rectangular cuboid, you must use the CUBOID_CONTAINER option. These options do not require any further information.

If you want to pack the ellipsoids inside a minimizing volume container, you must use the MINIMIZE_VOLUME option. This option does not require any further information.

Initial configuration

You can provide an initial configuration of the ellipsoids through the INITIAL_CONFIGURATION option. This option must be followed by the name of the file containing the initial arrangement of the ellipsoids. In the two-dimensional case, the content of this file must have the following format:

m
a1 b1 x1 y1 t1
a2 b2 x2 y2 t2
...
am bm xm ym tm

The first line must contain the number m of ellipses. Then, each one of the next m lines must contain the lengths of the semi-axes (a and b), the center (x and y) and the rotation angle (t) of an ellipse.

In the three-dimensional case, the content of this file must have the following format:

m
a1 b1 c1 x1 y1 z1 t1 u1 v1
a2 b2 c2 x2 y2 z2 t2 u2 v2
...
am bm cm xm ym zm tm um vm

The first line must contain the number m of ellipsoids. Then, each one of the next m lines must contain the lengths of the semi-axes (a, b, c), the center (x, y, z) and the rotations angles (t, u, v) of an ellipsoid. We have adopted a left-handed coordinate system and the ellipsoids are rotated through an angle t about the x-axis, through an angle u about the y-axis, and through an angle v about the z-axis, in this order.

For example, we could provide the following initial configuration for three three-dimensional ellipsoids in a file named initial-configuration.txt:

3
4.1 3.2 1.1 0.0  1.0  2.0  0.50 1.57  3.1415
2.3 2.3 2.1 3.3  4.1  5.9 -0.25 2.32 -0.7010
5.6 3.3 3.3 1.0 -3.1 -1.1  1.32 0.76  1.4562

In this example, the first ellipsoid has semi-axis lengths 4.1, 3.2 and 1.1, is centered at the point (0.0, 1.0, 2.0) and has rotation angles 0.5, 1.57 and 3.1415. Then, you should append the following line to your options file:

INITIAL_CONFIGURATION initial-configuration.txt

How to run

In order to execute the software, simply type the name of the executable file and the name of the options file. If your options file is called packing.opt for example, then you should execute the program as:

./packEllipsoids2D packing.opt

or

./packEllipsoids3D packing.opt

Further options

There are other options that can be set in order to solve your problem. Our method for packing ellipsoids implements a multi-start strategy to search for good quality solutions. It works as follows. At each iteration, an initial guess for the solution is constructed and then the optimization problem is solved starting from this initial solution.

The initial guess of the first iteration can be set by the INITIAL_SOLUTION_TYPE option. This option must be followed by a suitable type of initial guess, which is an integer number. In the two-dimensional case, the possible initial solution types are 1, 2, 3, 4, 5, 6, and 7. In the three-dimensional case, the possible initial solution types are 1 and 2.

For each of the subsequent iterations, the initial guess is given by a random perturbation of the most recent feasible solution found by the method. The PERTURBATION_FACTOR option defines how much the solution is perturbed. Its default value is 0. This option must be followed by a nonnegative real number. For example:

PERTURBATION_FACTOR 0.05

In this example, the solution will be perturbed by at most 5%, which means that the angles of rotations, the centers of the ellipsoids and the dimensions of the container (in case it is being optimized) are randomly perturbed by at most 5%.

It is also possible to perturb the first initial solution (that is defined by the INITIAL_SOLUTION_TYPE option). For this, you can use the INITIAL_SOLUTION_PERTURBATION_FACTOR option. For example:

INITIAL_SOLUTION_PERTURBATION_FACTOR 0.1

The multi-start strategy can be summarized as follows:

• Step 1. Construct an initial guess according to the INITIAL_SOLUTION_TYPE option and store it in x.
• Step 2. Perturb x according to the INITIAL_SOLUTION_PERTURBATION_FACTOR option.
• Step 3. Solve the nonlinear programming problem starting from the initial guess x.
• Step 4. If the solution found is feasible, store this solution in x.
• Step 5. Perturb x according to the PERTURBATION_FACTOR option.
• Step 6. Go to Step 3.

The number of multi-start iterations can be set through the NUMBER_MULTISTART_ITERATIONS option. This option must be followed by an integer number which is the number of iterations that the multi-start method will perform. For example, to execute 100 iterations, you should append the following line to the options file:

NUMBER_MULTISTART_ITERATIONS 100

It is also possible to not limit the number of multi-start iterations by providing a negative integer number:

NUMBER_MULTISTART_ITERATIONS -1

In this case, the method will continue executing and never stop. This choice is recommended. The user can manually stop the execution of the software once a sufficiently good quality solution has been found.

Solution output

By default, the solution found at the k-th iteration of the method is saved in a file named solution-k.txt. The format of the solution file in the two-dimensional case is the following:

d1 d2
m
a1 b1 x1 y1 t1
a2 b2 x2 y2 t2
...
am bm xm ym tm

The first line has the dimensions of the container. It can be the length and width of a rectangular container, the lengths of the semi-axes of an elliptical container, the length of the sides of a square (in which case this line has only one number) or the radius of a circle (in which case this line has only one number). The container is centered at the origin.

The second line contains the number m of ellipses packed. Then, each one of the next m lines contains the lengths of the semi-axes (a and b), the center (x and y) and the rotation angle (t) of an ellipse.

In the three-dimensional case, the solution file has the following format:

d1 d2 d3
m
a1 b1 c1 x1 y1 z1 t1 u1 v1
a2 b2 c2 x2 y2 z2 t2 u2 v2
...
am bm cm xm ym zm tm um vm

The first line has the dimensions of the container. It can be the length, width and height of a rectangular cuboid, the length of the sides of the cube (in which case this line has only one number), or the radius of a ball (in which case this line has only one number). The container is centered at the origin.

The second line contains the number m of ellipsoids packed. Then, each one of the next m lines contains the lengths of the semi-axes (a, b, c), the center (x, y, z) and the rotations angles (t, u, v) of an ellipsoid. We have adopted a left-handed coordinate system and the ellipsoids are rotated through an angle t about the x-axis, through an angle u about the y-axis, and through an angle v about the z-axis, in this order.

It is possible to change the prefix of the name of the output file through the OUTPUT_FILE_NAME_PREFIX option. For example, if you want the solution found at the k-th iteration to be stored in a file named output-k.txt, you should add the following line to your options file:

OUTPUT_FILE_NAME_PREFIX output

If you do not want the solutions of every iterations to be output, you can use the OUTPUT_ONLY_BEST_SOLUTION option. In this case, only the best solution found is output. Moreover, every time a better solution is found, it is output. This option does not require any further information. By default, the output file name is solution.txt The name of the output file can be set through the OUTPUT_FILE_NAME option. For example, if you want the output file to be named solution.out, then you should append the following options to your options file:

OUTPUT_ONLY_BEST_SOLUTION solution.out
OUTPUT_FILE_NAME

Notice that with the use of the OUTPUT_ONLY_BEST_SOLUTION option, every time a better solution is found, any previously solution stored in the output file is lost.