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...")
Example of Constraint File
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.