Random Placement Problem (RPP)

Hana Rudová
  and   Kamil Veømiøovský

Data Instances and Solutions


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.
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:

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).
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).
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).

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

Back to RPP main page.