

The random placement problem (RPP; for more details, see
) seeks to place a set of randomly
generated rectangles (called objects) of different sizes into a larger rectangle (called placement area) in such a way
that no objects overlap and all objects' borders are parallel to the border of the placement area. In addition, a set
of allowable placements can be randomly generated for each object. The ratio between the total area of all objects and
the size of the placement area will be denoted as the filled area ratio.
RPP allows us to generate various instances of the problem similar to a trivial timetabling problem. The correspondence
is as follows: the object corresponds to a course to be timetabled  the xcoordinate to its time, the ycoordinate to
its classroom. For example, a course taking three hours corresponds to an object with dimensions 3x1 (the course should
be taught in one classroom only). Each course can be placed only in a classroom of sufficient capacity  we can expect
that the classrooms are ordered increasingly in their size so each object will have a lower bound on its ycoordinate.
MPP instances were generated as follows: First, the initial solution was computed. The changed problem differs from the
initial problem by input perturbations. An input perturbation means that both x coordinate and y coordinate of a rectangle
must differ from the initial values, i.e. x!=xinitial & y!=yinitial. For a single initial problem and for a given number
of input perturbations, we can randomly generate various changed problems. In particular, for a given number of input
perturbations, we randomly select a set of objects which should have input perturbations. The solution to MPP can be
evaluated by the number of additional perturbations. They are given by subtraction of the final number of perturbations
and the number of input perturbations.
 
Each input problem (e.g., gen22.pl) has the following structure:
objects([
object(
name( rect1 ),
size( [ 2, 1 ] ),
valid_positions( [ 038, 013 ] )
),
object(
name( rect2 ),
size( [ 2, 1 ] ),
valid_positions( [ 038, 013 ] )
),
...
object(
name( rect200 ),
size( [ 2, 1 ] ),
valid_positions( [ 038, 713 ] )
)
] ).
Stating that the first rectangle (named rect1) has size 2x1 and its valid position are with x between 0 and 38, y between 0 and 13, and so on.
MPP instances contain an extra file with the solution (e.g., gen22.solution), with the following structure
assigned([[rect1X,[17]], [rect1Y,[5]], [rect2X,[24]], [rect2Y,[4]], ... [rect200X,[37]], [rect200Y,[10]]]).
Which means that the first rectangle (named rect1) is to be placed at [17,5], second at [24,4] and so on.
There is also a file (e.g., gen22.mpp) describing which input placements are to be prohibited (not that if the input placement is prohibited, it means that also all values with the same X or Y coordinate are prohibited). It has the following structure:
perturbation( 1, 0, [] ).
perturbation( 2, 0, [] ).
...
perturbation( 1, 2, [44,127] ).
perturbation( 2, 2, [80,153] ).
...
perturbation( 1, 4, [44,80,127,153] ).
perturbation( 2, 4, [48,67,138,170] ).
...
 
In the output folder, there are result.pl, stat.pl and stat.csv files.
As for initial problem, result.pl has the following structure:
result(1,1,0.156,200,248,
unassigned(0/[]),
assigned(400/[rect1X36,rect1Y8,rect2X0,rect2Y12,...])
).
For each solution, there is a term named result. It consists from:
 problem number (e.g., 1 means gen1.pl)
 test number (e.g., 1 means first run of that problem, up to RPP.NrTests
 time needed to solve the problem
 number of assigned variables (i.e., placed rectangles)
 number of iterations
 list of unassigned rectangles
 list of assigned rectangles (i.e., rect2X0 means that Xcoordinate of 2nd recnangle (named rect2) is assigned to 0)
Next, the content of file stat.pl is:
averages( problem( 1 ), time( 0.128 ), assigned( 200.000 ) ).
deviations( problem( 1 ), time( 0.015 ), assigned( 0.000 ) ).
averages( problem( 2 ), time( 0.162 ), assigned( 200.000 ) ).
deviations( problem( 2 ), time( 0.021 ), assigned( 0.000 ) ).
For each problem there is an average number (term averages) and RMS (term deviations) of the time need to solve the problem (in seconds) and number of assigned variables.
Finally, the content of file stat.csv is:
gen;time[s];timeRMS;assigned;assignedRMS;iters;itersRMS
1;0.128;0.015;200.000;0.000;241.800;9.642
2;0.162;0.021;200.000;0.000;363.800;59.057
3;0.219;0.038;200.000;0.000;516.400;85.994
It is a table of problem number, average time (in seconds), RMS time, average number of assigned variables, RMS number of assigned variables, average number of iteratons and RMS number of iterations.
As for minimal perturbation problem (MPP), the content of above files is a bit different. File result.pl:
result(1,0,0.078,200,260,
unassigned(0/[]),
perturbations(0/[])
).
result(1,4,0.062,200,280,
unassigned(0/[]),
perturbations(10/[rect44X3,rect44Y11,rect80X28,rect80Y12,rect104X5,rect104Y11,rect127X8,rect127Y12,rect153X33,rect153Y11])
).
For each solution, there is a term named result. It consists from:
 test number (e.g., 1 means first run of that problem, up to RPP.NrTests
 number of input perturbations (it goes from 0 to 200, incremented by 4 in each step)
 time needed to solve the problem
 number of assigned variables (i.e., placed rectangles)
 number of iterations
 list of unassigned rectangles
 list of perturbations rectangles (i.e., rectangles assigned to different than initial locations)
File stat.pl:
averages( initperturbations( 0 ), time( 0.078 ), assigned( 200.000 ), perturbations( 0.000 ) ).
deviations( initperturbations( 0 ), time( 0.000 ), assigned( 0.000 ), perturbations( 0.000 ) ).
averages( initperturbations( 4 ), time( 0.062 ), assigned( 200.000 ), perturbations( 5.000 ) ).
deviations( initperturbations( 4 ), time( 0.000 ), assigned( 0.000 ), perturbations( 0.000 ) ).
For each number of input perturbations there is an average number (term averages) and RMS (term deviations) of the time (in seconds), the number of assigned rectangles and the number of perturbations.
File stat.csv:
pert;time[s];timeRMS;assigned;assignedRMS;perturbations;perturbationsRMS;iters;itersRMS
0;0.078;0.000;200.000;0.000;0.000;0.000;260.000;0.000
4;0.062;0.000;200.000;0.000;5.000;0.000;280.000;0.000
8;0.078;0.000;200.000;0.000;9.000;0.000;408.000;0.000
For each number of input perturbations there is an average number (term averages) and RMS (term deviations) of the time (in seconds), the number of assigned rectangles, the number of perturbations and the number of iterations.
 
Usage:
java Xmx512m cp ifs1.2 net.sf.cpsolver.ifs.example.rpp.Test file.cfg [output_dir]
file.cfg ... configuration file
output_dir ... output folder
Example:
java Xmx512m cp ifs1.2.jar net.sf.cpsolver.ifs.example.rpp.Test rpp80.cfg .\output\rpp80
java Xmx512m cp ifs1.2.jar net.sf.cpsolver.ifs.example.rpp.Test mpp12.cfg .\output\mpp12
Output:
Output is located in the folder output_dir\<date> .
Example configuration files: [RPP(80%)] [MPP(gen12)]
For more details about the problem implementation and parameters (i.e., content of the configuration file file.cfg ), please consult the documentation of the main class and the problem (package ).

