Random Placement Problem (RPP)

 Hana Rudová hanka@fi.muni.cz and Kamil Veømiøovský xvermir@fi.muni.cz

Data Instances and Solutions

Description

The instances are divided into sets by their filled area ratio. We have generated instances involving 200 objects of the dimensions 2x1, 3x1, 4x1 and 6x1. The probabilities that an object would have a given width, the list of different lower y-bounds (as percentages of the height of the placement area), and their probabilities were chosen to roughly correspond to our real-life timetabling problem. They were the same for all instances and can be found at the beginning of each definition file.

Each of the instances is in a separate file, which contains the instance definition and also basic information about the instance as comment lines. For the syntax of the file, see below. The basic information consists of the above mentioned probabilities and the following:

Number of objects
A number of objects the instance involves.
Area
Dimensions of the placement area. For different sets, the different dimensions are chosen to meet the filled area ratio.
Total area of objects
Total sum of areas of all objects.
Area filled up with objects
The filled area ratio of the instance.
Average Y lower bound
Average lower y-bound of an object.

Syntax of Definition Files

The syntax of the definition file meets the usual prolog syntax. Any line starting with % is a comment line and is ignored. The RPP instance is defined by a predicate objects/1, which contains a list of all objects. Each object is again a predicate. It has the following form:

object(name(Name), size([Width, Height]), valid_positions([Xmin-Xmax, Ymin-Ymax])).

All above variables must be instantiated and have the following meanings:

Name
The name of the object. Always rectX, where X is the numerical order of the object.
Width, Height
Objects dimensions. Height is always 1 (course is taught in one and only one room).
Xmin-Xmax
Allowed x-coordinates of the object. Always 0-X, where X is the placement area width decreased by the object's width (any time slot is allowed for any course).
Ymin-Ymax
Allowed y-coordinates of the object. Always Y1-Y2, where Y2 is the placement area height decreased by the object's width decreased by 1 (y coordinates are counted from 0), and Y1 is randomly generated lower y-bound of the object (using probabilities mentioned above).

Syntax of Solution Files

The solution file contains a predicate assigned/1 with a list of all objects' coordinates in the following form: each element of the list in the form [Name,[Value]], where Name consists of the name of an object and a letter X or Y, meaning x or y coordinate of the object, and Value is the correspoding coordinate, e.g., [rect129Y, [12]].

Some instaces were solved partially. A predicate unassigned/1 informs about the number of unplaced objects.

To each file gen*.pl, containing an instance definition, corresponds the file gen*.solution, containing the solution of the instance (if succesffully solved). For other instances, the file gen*.partial contains a partial solution of the problem (only some objects were placed).

• 80.tar.gz - filled area ratio 80 % (all 50 problems completely solved);
• 85.tar.gz - filled area ratio 85 % (47 problems completely solved);
• 90.tar.gz - filled area ratio 90 % (23 problems completely solved);
• 95.tar.gz - filled area ratio 95 % (6 problems completely solved).
• 100.tar.gz - filled area ratio 100 % (4 problems completely solved).
• 105.tar.gz - filled area ratio 105 % (all problems are over-constrained).
• 110.tar.gz - filled area ratio 110 % (all problems are over-constrained).

Please let us now about any improvements (more problems solved or more objects assigned).

Back to RPP main page.