Constraint Files Explained

I've received a number of queries regarding the structure of the constraint files used by my thesis, lecture timetabling using genetic algorithms, so i've decided to post up a page describing the format of these files.

Description of Constraint File

A constraint file is a simple text file, whose name has the extension ".ctr" It stores the specification of a university - its classes, its lecturers and its classrooms.

These files can be written in any text editor.

Each piece of data within the file is stored on a new line. I expect that new lines were marked with a Carriage Return and a Line Feed (character 13 and character 10 respectively, \r\n) though from inspecting the code it seems you only need a line feed character (Character 10, referred to as "\n" or "new line" in the C Language).

Structure of Constraint File

Now I will go through line by line, explaining what the constraint file contains

line 1 and 2: are for comments and are thus ignored (for example line 1 may contain the name of the test and line 2, the name of the university)

line 3: contains the number of classes

line 4: contains the number of class associations. (for example: the number of courses, departments or faculties) (two classes are "associated" if they can't be held at the same time, because for example, they share a lot of students.)

For the remainder of the file, I cannot give specific line numbers (as I did above). So I instead I will just say 'Next line'.

The following section is repeated for each class (e.g., if there are three classes, this section will repeat three times)

Next line: Name of class

Next line: Reference Num of lecturer

Next line: Size of class

Next line:X location of class' administrative office

Next line:Y location of class' administrative office

Next line: class association code (example, course/year code)

(If two classes can be held at the same time, then they would have the same value in their 'class association code')

Next line: the number of lecturers

The following section is repeated for each lecturer:

(e.g., if there are six lecturers, this section will repeat six times)

   Next line: Name of lecturer
   Next line: X location of lecturers office
   Next line: Y location of lecturers office
   For each day of the week:
     for each hour of the day:
        A character that represents the availability of the lecturer
     next hour
    Move to next line   
   next day

Next line: the number of rooms

The following section is repeated for each room:

(ie, if there are eight rooms, this section will repeat eight times)

For each room:
   Next line: the name of the room
   Next line: the capacity of the room
   Next line: the X location of the room
   Next line: the Y location of the room
   for each day of the week:
     for each hour of the day:
        A character that represents the availability of the room 
     next hour
    Move to next line   
   next day

SO... to try and demonstrate this, i've written an example constraint file (I can't test it unfortunately...) for a university called 'The Tiny University'

This university holds two classes, Biology101 and Biology102. They cannot be held at the same time as each other, so I've given them the same "Class Assocation Code" (i gave them both a Class Assocation Code of "1").

Biology101 has fifty students and is taught by lecturer number 1 (whose name turns out to be Prof Freddy101)

Biology102 has seventy students and is taught by lecturer number 2 (whose name turns out to be Dr Jenny102)

The home office for Biology101 is located at co-ordinates 10,10.

While the home office for Biology102 is located at co-ordinates 20,20.

There is only 1 room in this rather tiny university, and that room is called "The Green Room."

the Green room holds up to 75 students and is located at co-ordinates 10,10.

Okay that explains most of the file - but now to explain what is initially the most daunting section: the "Availability Matrix".

That is the section that look like this:

1O1OO1O1O1
1111OOOO11
11OO11O1O1
11O1O1O1OO
O111O111O1

And you will find one "Availability Matrix" for each resource, be it a lecturer or a classroom.

There are three resources in the tiny university (two lecturers plus one classroom) hence you will see three availability matrices.

Each matrix is five line long, representing the five days of the week, monday to friday.

Each line is ten characters long, representing ten working hours of the day.

Each character is either a one or a zero, represting "available" and "not available" respectively.

So if for example you look at the availability matrix under Doctor Jenny102, you will see that in the third line of the matrix (representing wednesday -- the third day of the working week), there is a line that looks like this: 1100110000, representing Jenny's availability on a wednesday. What this means is that she is available for the first two hours of the day, unavailable for the next two hour, available for the two hours after that and then unavailable for the final four hours of the working day.

Availability here relates to prior commitments, and so forth. For example if a lecture hall was booked out to an external party every monday morning, then you would expect to see a few zeros on the first line of the availability matrix for that resource.

OKAY - here's the example constraint file (copy it into a file and rename it Constr3.ctr) (starting with the line 'Test: x16...")

Test: x16021
THE TINY UNIVERSITY
2
1
Biology101
1
50
10
10
1
Biology102
2
70
20
20
1
2
Prof Freddy101
30
30
1001001010
1111000011
1100110101
1101010100
0111011101
Doctor Jenny102
7
7
1000110101
1110100011
1100110000
1101010100
0111011101
1
The Green Room
75
10
10
1100010101
1111000011
1101010000
1100100100
0111101101

My book "Choose Your First Product" is available now.

It gives you 4 easy steps to find and validate a humble product idea.

Learn more.