Random Placement Problem (RPP)

Data Instances and Solutions

• Description
• Syntax of Definition Files
• Syntax of Solution Files
• Download

Description

The instances are divided into sets of 50 problems by their filled area ratio. Instances involving 200 objects of the dimensions 2x1, 3x1, 4x1 and 6x1 were generated employing the RPP generator. 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. Another set of 50 problems was generated with double domain sizes. It concerns 800 objects and and all problems have filled area of 90 %.

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.

Download

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

• 75.tar.gz - filled area ratio 75 % (49 problems completely solved);
• 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).
• double.tar.gz - problems with double domain size (1 problem completely solved).

Back to the main page.