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 respective 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-3.tar.gz that you have downloaded:

tar -zxvf packing-ellipsoids-3.tar.gz

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

cd packing-ellipsoids-3

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-3 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-3 directory, type make to compile the code:

make

After the compilation, an executable file called packEllipsoids2D or packEllipsoids3D, depending on the chosen dimension, 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 thing you should do is to define the sizes of the semi-axes of the ellipsoids to be packed. Two options are available: IDENTICAL_ELLIPSOIDS and RANDOM_ELLIPSOIDS. If the ellipsoids you would like to pack are all identical, i.e., they all have the same semi-axis lengths, then you can use the first 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 and their semi-axis lengths are uniformly random distributed, then you can use the RANDOM_ELLIPSOIDS option. This option must be followed by either four numbers (in case you want to pack two-dimensional ellipsoids) or six numbers (if you want to pack three-dimensional ellipsoids). These numbers specify the intervals in which each of the semi-axis lengths belongs to. For example, if you want to pack two-dimensional ellipsoids whose length of the first semi-axis takes values in the interval [0.75, 1.25] and whose length of the second semi-axis takes values in the interval [0.25, 0.95], the following line should be appended to the options file:

RANDOM_ELLIPSOIDS 0.75 1.25 0.25 0.95

Analogously, for packing three-dimensional ellipsoids whose lengths of the semi-axes take values in the intervals [0.75, 1.25], [0.25, 0.95], and [0.45, 0.55], the following line should be appended to the options file:

RANDOM_ELLIPSOIDS 0.75 1.25 0.25 0.95 0.45 0.55

Container

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

In the two-dimensional case, the container can be a ball, a square, or an arbitrary rectangle. In the three-dimensional case, the container can be a ball, a cube, or an arbitrary cuboid. All containers are centered at the origin. The rectangular (or cuboidal) containers have their sides 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 ball, you should use the BALL_CONTAINER option. In order to maximize the compatibility of the format of the options file with that of previous versions, this options does not require any further information. To specify the radius of the container, the option BALL_CONTAINER_RADIUS must be used. For instance, to pack ellipsoids within a ball of with radius 5, the following lines should be appended to the options file:

BALL_CONTAINER
BALL_CONTAINER_RADIUS 5

To pack the ellipsoids within a square or a cube, use the SQUARE_CONTAINER or CUBE_CONTAINER option. To specify the length of the side of the square or cube, use the SQUARE_CONTAINER_SIDE_LENGTH or CUBE_CONTAINER_SIDE_LENGTH option. For instance, to pack ellipsoids within a square or cube whose side length is 50, the following lines could be added to the options file:

CUBE_CONTAINER
CUBE_CONTAINER_SIDE_LENGTH 50

In general, to pack ellipsoids within a rectangle or cuboid, the RECTANGLE_CONTAINER or CUBOID_CONTAINER option and should be used. To specify the lengths of the sides of the rectangle, the RECTANGLE_CONTAINER_SIDE_LENGTHS or CUBOID_CONTAINER_SIDE_LENGTHS option should be used. These options are followed by either two numbers (in the two-dimensional case) or three numbers (in the three-dimensional case), which are the lengths of the sides of the rectangle or cube. For instance, to pack ellipses within a rectangle with sides 20 and 15, the following options should be used:

RECTANGLE_CONTAINER
RECTANGLE_CONTAINER_SIDE_LENGTHS 20 15

In the three dimensional case, for example, one could use the options

CUBOID_CONTAINER
CUBOID_CONTAINER_SIDE_LENGTHS 50 30 20

to pack ellipsoids within a cuboid whose sides have lengths 50, 30, and 20.

Objective

It is also necessary to specify how the ellipsoids are packed. When an ellipsoid is packed, some of its "height" is minimized. We define three heights associated with an ellipsoid: the lower, the upper, and the middle height. Letting n denote the dimension of the problem (2 or 3), the lower height is defined as min{ x_n | x belongs to the ellipsoid } and the upper height is defined as max{ x_n | x belongs to the ellipsoid }, where x_n denotes the n-th component of the n-dimensional vector x. The middle height is defined to be the last component of its center. So, if an ellipsoid has center c, its middle height is c_n.

To indicate that the lower, upper, or middle height must be minimized, one should use the MINIMIZE_LOWER_HEIGHT, MINIMIZE_UPPER_HEIGHT, and MINIMIZE_SUM_CENTERS options, respectively. It is also possible to minimize a "random height", which is a random convex combination of the lower and upper heights. For minimizing a random height, the MINIMIZE_RANDOM_HEIGHT option must be used.

Notice that only one of these options should be used. If you do not know which of these options should be chosen, we recommend using MINIMIZE_SUM_CENTERS.

Isolation constraints

Isolation constraints aim at reducing the complexity of packing each ellipsoid by requiring the new ellipsoid to be packed to be confined within a small region of the container, thus reducing the number of non-overlapping constraints. We refer the user to the paper [1] for a detailed explanation of the isolation constraints.

We define two types of isolation constraints. The first one constrains the new ellipsoid to remain within a hyperrectangle with infinite height. To use this isolation constraint, one should add the BOX_ISOLATION_CONSTRAINT option to the options file. Let b denote the largest length of a semi-axis of the new ellipsoid to be packed. This option is followed by the value that, when multiplied by b, gives the length of the sides of the hyperrectangle. For instance, one could add

BOX_ISOLATION_CONSTRAINT 10

to the options file to use this isolation constraint having a hyperrectangle with side length 10b.

The second type of isolation constraint requires the new ellipsoid to lie above a certain plane parallel to the x-plane (in the two-dimensional case) or the x-y plane (in the three-dimensional case). To activate this isolation constraint, the LOWER_HYPERPLANE_ISOLATION_CONSTRAINT option must be used. This option must be followed by a value that determines at which point the plane must pass through. For instance, if we use

LOWER_HYPERPLANE_ISOLATION_CONSTRAINT 5

then the height of the plane will be defined as h - 5b, where h is the largest middle height of an ellipsoid that is already packed and that may intersect the region defined by the first isolation constraint.

These options can (and in most cases should) be used together. If you want to pack a relatively small number of ellipsoids, you may try first running without any of these options. If you do not know which values should be chosen for these options, you could begin using the values given in the examples above as a rule of thumb and then adapt them in order to improve the quality of the solutions and/or reduce the computational time.

Ideally, the presence of isolation constraints should not affect the quality of the solution. The largest the values to these options are, the higher is the expected quality of the solutions. However, the largest these values are, the higher is the computational effort required to solver the problem. Thus, one should carefully choose the values of these parameters.

How to run

In order to execute the program, 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 help solve your problem. They will be added to this section in the future.

Solution output

By default, the current best solution found is saved in a file named solution.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 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.