The PackLib² File Format

The PackLib² file format is based on the XML standard. For every article that is listed in PackLib² there is one XML file. Each of these files contains a mandatory descriptive section. If new problem instances are defined these instances are listed in the problem section. Computational results are listed in a results section.

These three sections are bracketed by

The name attribute is mandatory. It serves as the file name and is used throughout PackLib² to reference this file. In the format string for the name attribute the a denotes the first letter of the last name of the first five authors. The t stands for the first letter of the first five nouns of the title. The two y give the publication year of the article. This format string closely follows the referncing style of geom.bib

Most features of PackLib² will be demonstrated by example. These examples are based on the article "An Exact Two-Dimensional Non-Guillotine Cutting Tree Search Procedure" by J.E. Beasley which appeared in 1985. Thus the filename of this instance is b-etdng-85.xml and the name attribute reads b-etdng-85.

Description Section

The description section gives general information about the article. It is divided into two parts. The mandatory first part gives the source of the article. It's entries are based on the BiBTex-Format. In the optional second part an abstract can be given.

The following example illustrates a typical description section:

up.gif

Problem Section

If new problem instances are defined in the article the XML file contains a problem section. In this section the characteristics of the problem instances are given in detail.

Normally the problem section should begin with a <Name> tag. The name specified here is used throughout PackLib² to identify the problem instances as a whole.

There are a few tags that help to identify the type of the problem instance. The <Type> tag is based on the improved typology of cutting and packing problems proposed by G. Wäscher, H. Haußner, and Holger Schumann. The dimension of the problem must be given using the <Dimension> tag. If applicable the number of <GuillotineCuts> can be specified.

Each single instance is defined by the <Problem name=string> tag. The name attribute is used to reference the problem instance relative to the XML file throughout PackLib². Each instance falls into two parts. The first part is concerned with the containers. The second part deals with the boxes that are to be packed in the containers.

Container Section

Each container is defined with the <Container type=string> tag. The type attribute should be unique within the current problem.

The size of the container is specified through tags labeled <x1>, <x2>, ... . There have to be as many different tags as specified by <Dimension>. If the problem is an open dimension problem this can be indicated by putting an inf instead of a number. In the following example

a container of type 1 that is 30 units wide and of infinite height is defined.

If there is a minimal number of containers of a given type that is to be used or if there is an upper bound on the number of containersw of a given type that can be used this can be expressed by the <minCount> and <maxCount> tags respectively.

If there is a cost associated with a container it can be given with the <cost> tag.

Box Section

In general the container section and the box section do not differ. A new box is defined with the help of the <Box type=string> tag. All the other tags are the same as for the containter section. There is one additional tag for boxes. If a box is orientable this is indicated by the empty tag <Orientable />.

Example of a Problem Section

The following excerpt from b-etdng-85.xml illustrates the structure of the problem section.

up.gif

Result Section

The result section lists all the computational results given in the article. General information about the results like the type of computer the results were obtained on can be specified with the <Machine> tag. More information about the results can be given with a <Note> tag.

For each result obtained there is a corresponding <Result ref=aaaaa-ttttt-yy name=string> tag. The ref attribute indicates in which file the problem was defined. The name attribute gives the name of the problem that was solved.

There are different kinds of solutions that are stored in PackLib². The <Type> specifies whether a lower bound, an upper bound, or an optimal solution has been obtained. The value of the solution is given with the <Value> tag. The time in seconds needed to obtain the solution is given with the <Time> tag.

If a description of a solution is available it is stored in the <Description> tag. For each container used there is a <Container type=string> tag. Inside this tag there is a <Box type=string> tag for each box that is placed in this container. The tags <p1>, <p2>, ... give the position of the box inside the container.

A result section might look like this.

up.gif